COMMUNITY DETECTION IN SOCIAL NETWORKS EMPLOYING COMPONENT INDEPENDENCY.

Many networks, including social and biological networks, are naturally divided into communities. Community detection is an important task when discovering the underlying structure in networks. GN algorithm is one of the most influential detection algorithms based on betweenness scores of edges, but it is computationally costly, as all betweenness scores need to be repeatedly computed once an edge is removed. This paper presents an algorithm which is also based on betweenness scores but more than one edge can be removed when all betweenness scores have been computed. This method is motivated by the following considerations: many components, divided from networks, are independent of each other in their recalculation of betweenness scores and their split into smaller components. It is shown that this method is fast and effective through theoretical analysis and experiments with several real data sets, which have acted as test beds in many related works. Moreover, the version of this method with the minor adjustments allows for the discovery of the communities surrounding a given node without having to compute the full community structure of a graph. [ABSTRACT FROM AUTHOR]