Volume 7 Number 1 (Jan. 2012)
Home > Archive > 2012 > Volume 7 Number 1 (Jan. 2012) >
JSW 2012 Vol.7(1): 204-211 ISSN: 1796-217X
doi: 10.4304/jsw.7.1.204-211

A Heuristic Algorithm for Bipartite Community Detection in Social Networks

Chengying Mao

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


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

General Information

ISSN: 1796-217X (Online)
Frequency:  Quarterly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, CNKIGoogle Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Apr 26, 2021 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Nov 18, 2021 News!

    Papers published in JSW Vol 16, No 1- Vol 16, No 6 have been indexed by DBLP   [Click]

  • Dec 24, 2021 News!

     Vol 15, No 1- Vol 15, No 6 has been indexed by IET-(Inspec)   [Click]

  • Jan 04, 2024 News!

    JSW will adopt Article-by-Article Work Flow

  • Dec 06, 2019 News!

    Vol 14, No 1- Vol 14, No 4 has been indexed by EI (Inspec)   [Click]