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: Monthly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Aug 21, 2019 News!

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

  • Jun 25, 2019 News!

    Vol.13, No.9 has been indexed by EI (Inspec).   [Click]

  • Aug 01, 2018 News!

    [CFP] 2019 the annual meeting of JSW Editorial Board, ICCSM 2019, will be held in Barcelona, Spain, July 14-16, 2019.   [Click]

  • Jul 10, 2019 News!

    Vol 14, No.8 has been published with online version 4 original aritcles from 2 countries are published in this issue.    [Click]

  • Jul 22, 2019 News!

    Welcome Prof Ferhat Khendek from Canada to join the Editorial board of JSW    [Click]