Twitter and The Social Graph

1. Extract social-graph strucutre using Twitter API

Twitter API is used to extract the data of ego-network i.e. the nodes followed by self (that’s me), and first-degree ‘Follows’ of those nodes. This Graph of (Vertices, Edges) is used to build an adjacency matrix.

2. Identify influential friends using ‘Page Rank’ formulation

From the adjacency matrix, we can create a column-stochastic matrix (aka Markov transition matrix in random-surfer model) such that, a column with m outlinks will have 1/m as value in respective m cells.

binaryMap_cfr      = binaryMap_rfc.transpose()            # column-values: Outlinks
binaryMap_cfr_norm = binaryMap_cfr / binaryMap_cfr.sum(axis = 0)
colStochMatrix = np.matrix( binaryMap_cfr_norm.fillna(0)) # column-stochastic-matrix

Initialize PageRank vector such that all nodes have equal PageRank score, adding upto 1.

pageRankVector = np.matrix([1.0/len(index)] *  len(index)) # iniitialize page-rank-vector 
pageRankVector = pageRankVector.transpose()                # transpose to column-vector

On applying Transition-matrix transformation iteratively on PageRank vector, vector will eventully converge such that: Matrix.Vector = Vector. Equivalently, this is eigen-vector formulation with PageRank vector being the principal eigen-vector corresponding to eigen-value 1 [Since it’s a column-stochastic matrix, principal eigen-value is 1].

Note : To understand how PageRank works, this interactive tutorial from Setosa is a good place to start.

while epsilon > (1.0/(10**16)):
    pageRankVectorUpdating = colStochMatrix * pageRankVector * beta 
    
    # re-insert leaked page-ranks
    S                      = np.array(pageRankVectorUpdating).sum()                      
    pageRankVectorUpdated  = pageRankVectorUpdating + 
               (1 - S) * (1.0/len(index)) * np.ones_like(len(index))
    
    # compute the squared-difference and check for convergence
    error                  = np.array(pageRankVectorUpdated - pageRankVector)
    epsilon                = np.sqrt((error *  error).sum())   
    pageRankVector         = pageRankVectorUpdated    

Sum of Page-Rank Scores: 1.0
Converged in 58 iterations

3. Identify implicit clusters

Ideally, the number of clusters are decided using a plot of within-cluster sum-of-squares-of-distances vs number of clusters. Here for simplicity, we use a simple heuristic to fix the number of clusters in advance (~ 10 clusters)

Here we are more interested in clustering behavior which surfaces from who-follows-me (network-driven) graph, rather than who-do-I-follow (self-driven). So the plan is to represent nodes as Observations and whether other nodes follow them or not (1 or 0) as Features (One Observation per row, and one Feature per column) Thus the input matrix must be such that any value in cell implies whether node in the column follows node in the row.

est = KMeans(max_iter = 100000, n_clusters = n_clusters, n_init = 200, init='k-means++')  
results_df['kmeans'] = est.fit_predict(binaryMap_cfr)

spectral = cluster.SpectralClustering(n_clusters=n_clusters,  n_init = 500,
                                          eigen_solver='arpack',
                                          affinity="nearest_neighbors")
spectral.fit(binaryMap_cfr)
results_df['spectral'] = spectral.labels_.astype(np.int)

pca = PCA(n_components=3)
Xproj = pca.fit_transform(binaryMap_cfr)

print("Explained-variance, Proportion of Explained-variance in 3 dims [dim1 dim2 dim3]")
print(pca.explained_variance_, pca.explained_variance_ratio_)

Explained-variance, Proportion of Explained-variance in 3 dims [dim1 dim2 dim3]
[ 7.09266174  3.16212677  1.21891396] [ 0.18363161  0.08186862  0.03155813]

4. Recommend new friends to follow

Now that we have PageRank of nodes and clusters they belong to, we can ask for recommendations on the basis of nodes followed by top-ranked nodes, across graph or specific to a cluster of interest.

5. Social Graph (Nodes, Links) in 3d space (using igraph)

In the PCA section, we saw the nodes visualized in 2D space. igraph module offers richer network-analysis capabilities in R. Let’s visualize nodes in 3D by using igraph and threejs packages in R.

For simplicity, let’s look only at important nodes: say, nodes with >50 inlinks in initial ego-network. Colors correspond to Spectral Clustering output and node-size is proportional to PageRank. Three dimensions from Principal Component Analysis output are used to fix nodes in 3D space.

( Press and hold the left mouse button and move the mouse to rotate the plot. Press and hold the right mouse button to pan. Use the mouse scroll wheel to zoom. Hover mouse-pointer over node-centre to display FullName)