COMMUNITY DETECTION IN SOCIAL NETWORKSEMPLOYING COMPONENT INDEPENDENCY

摘要

Many networks, including social and biological networks, are naturally divided into com-munities. Community detection is an important task when discovering the underlyingstructure in networks. GN algorithm is one of the most influential detection algorithmsbased on betweenness scores of edges, but it is computationally costly, as all betweennessscores need to be repeatedly computed once an edge is removed. This paper presentsan algorithm which is also based on betweenness scores but more than one edge can beremoved when all betweenness scores have been computed. This method is motivated bythe following considerations: many components, divided from networks, are independentof each other in their recalculation of betweenness scores and their split into smaller com-ponents. It is shown that this method is fast and effective through theoretical analysisand experiments with several real data sets, which have acted as test beds in many re-lated works. Moreover, the version of this method with the minor adjustments allows forthe discovery of the communities surrounding a given node without having to computethe full community structure of a graph.