“Follow the Leader”: A Centrality Guided Clustering and Its Application to Social Network Analysis

Abstract EN

Within graph theory and network analysis, centrality of a vertex measures the relative importance of avertex within a graph.

The centrality plays key role in network analysis and has been widely studiedusing different methods.

Inspired by the idea of vertex centrality, a novel centrality guided clustering(CGC) is proposed in this paper.

Different from traditional clustering methods which usually choose theinitial center of a cluster randomly, the CGC clustering algorithm starts from a “LEADER”—a vertexwith the highest centrality score—and a new “member” is added into the same cluster as the “LEADER” whensome criterion is satisfied.

The CGC algorithm also supports overlapping membership.

Experiments onthree benchmark social network data sets are presented and the results indicate that the proposed CGCalgorithm works well in social network clustering.