School of Software and Communication Engineering, Jiangxi University of Finance and Economics, 330013 Nanchang, China

---

Abstract—Analysis on topological characteristics of the network, such as the vertex degree distribution, centrality and community structure, provides valuable insight into the structure and function of the interacting data entities. Community detection is one of the key problems in the field of social network analysis. In the paper, we mainly focus on the two-part division problem for network, i.e., community (or graph) partitioning. Based on the in-depth analysis on the community features of some known partitioning results, a three-stage heuristic algorithm named 3SHP is proposed. At first, two pseudo-centers are identified according to the clue of the diameter path in a network. Then, two heuristic strategies, i.e. the shortest path cutting (SPC) and two-point diffusing (TPD), are introduced to divide the whole network into three parts: two rudimental communities and a set of undecided nodes. Subsequently, an experience rule is used to classify such undecided nodes to produce two final communities. The experiment results show that the 3SHP algorithm is effective, able to yield the best partitioning results in most instances.

Index Terms—heuristic method, graph algorithm, algorithm design and analysis, social networks

[PDF]

Cite:Chengying Mao, "A Heuristic Algorithm for Bipartite Community Detection in Social Networks," Journal of Software vol. 7, no.1, pp. 204-211, 2012.