## Convexified Modularity Maximization for Community DetectionIn many modern systems, e.g., recommender systems, similar objects form hidden clusters and we are interested in recovering the clusters based on observation of pairwise interactions among the objects. The data of pairwise interactions can be represented as a graph consisting of nodes representing objects and edge connections encoding pairwise interactions. Community detection aims to find the clusters, i.e., the dense subgraphs, in a large graph. We propose a new methodology for community detection. It is based on a semidefinite programming relaxation
of the classical (generalized) modularity maximization formulation, followed by a doubly weighted L1-norm k-median
clustering: On the left, we show a facebook friendship network formed by students at Simmons College. Nodes are colored according to the clustering result of convexified modularity maximization. The 4 clusters are found to be correlated with the graduation years. ## Semidefinite programming (SDP)
Let $A$ denote the adjacency matrix of graph $G$, and $d$ denote the vector of node degrees.
k=k+1
end while 3. Output the final solution . ## Doubly weighted k-median clusteringThe $i$-th row of $\widehat{Y}$ can be viewed as a feature vector for node $i$, and one can cluster nodes by clustering the corresponding rows of $\widehat{Y}$. Here we multiply the columns of $\widehat{Y}$ by the corresponding degrees to obtain $\widehat{W}=\widehat{Y} {\rm diag}(d)$. The $i$-th row of $\widehat{W}$ can be viewed as a weighted feature vector. Next we cluster the row vectors of $\widehat{W}$ using a weighted k-median clustering. In particular, we solve the following program for a partition $C_1,...,C_r$ of $[n]$ and $r$ cluster centers $x_1,...,x_r \in \mathbb{R}^n$: ## CodeWe provide the matlab source code for our algorithm## PaperYudong Chen, Xiaodong Li, and Jiaming XuConvexified modularity maximization for degree-corrected stochastic block models arXiv:1512.08425. Dec. 2015. ## People |