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

[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.

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
  • Dec 06, 2019 News!

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

  • Nov 18, 2019 News!

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

  • Dec 06, 2019 News!

     Vol 13, No 10- Vol 13, No 12 has been indexed by EI (Inspec)   [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Jun 25, 2019 News!

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