A Three-Phase Hierarchical Algorithm for Detecting Community Structure

DOI

10.2991/ccit-14.2014.12How to use a DOI?

Keywords

social network, community structure, modularity, hierarchical algorithm, cluster.

Abstract

Social networks, such as Facebook, Twitter, Renren, Sina Weibo, are rising rapidly in the past dozen years and are taking a more and more important role in our daily life. There’s a common feature for social networks: they can be divided into subgroups, within which the network connections are dense, but between which they are sparse. The subgroup is known as community, also named group, cluster or module. Community structure detecting can help discover the potential of social networks. This paper will propose a new algorithm based on the fast GN algorithm in pursuit of an improvement in quality. The algorithm consists of three phases. In the first phase, network will be divided based on the prior knowledge of the degree, during which time, the node with the highest degree in the network will group its neighbor according to a threshold; in the second phase, agglomeration will be done just like the fast GN algorithm; in the third phase, we try to achieve a better community structure by individual vertex moving. In the experiment, our algorithm will be compared with the fast improved GN algorithms and results show that our algorithm has a better in terms of the modularity and NMI, which are the index to measure the quality of community structure, and are proposed respectively by Newman and Lancichinetti.

Copyright

© 2014, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Qiong Hu
AU  - Gongshen Liu
PY  - 2014/01
DA  - 2014/01
TI  - A Three-Phase Hierarchical Algorithm for Detecting Community Structure
BT  - Proceedings of the 2014 International Conference on Computer, Communications and Information Technology
PB  - Atlantis Press
SP  - 38
EP  - 41
SN  - 1951-6851
UR  - https://doi.org/10.2991/ccit-14.2014.12
DO  - 10.2991/ccit-14.2014.12
ID  - Hu2014/01
ER  -