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 for the discovering underlying structure in networks. GN algorithm is one of the most influential detection algorithms based on betweenness scores of edges, but it is computationally cosly, as all betweenness scores should be repeatedly computed once an edge is removed. Here, an algorithm is presented, 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 consideration: many components, divided from networks, are independent 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 been acted as test beds in many related works.