Overlapping community detection algorithm based on fuzzy hierarchical clustering in social network

被引：0

作者：

School of Electronics and Information Engineering, Xi'an Jiaotong University, Xi'an ^{[1
]}

710049, China

不详 ^{[2
]}

710049, China

机构：

[1] School of Electronics and Information Engineering, Xi'an Jiaotong University, Xi'an

[2] Shaanxi Province Key Laboratory of Computer Network, Xi'an Jiaotong University, Xi'an

来源：

Hsi An Chiao Tung Ta Hsueh | / 2卷 / 6-13期

关键词：

Fuzzy hierarchical clustering; Overlapping community detection; Similarity; Social network;

D O I：

10.7652/xjtuxb201502002

中图分类号：

学科分类号：

摘要：

A detection algorithm for overlapping communities based on fuzzy hierarchical clustering, CDHC, is proposed to detect the overlapping communities and to solve the fuzzy and hierarchical relationships among communities in social networks. The algorithm first utilizes the distance weighting factors to calculate the similarity among communities, and the communities with similarity larger than a given threshold are then merged together. The membership grade of each node for the merged community is computed and nodes with membership grades less than a given threshold are removed from the community to form a structure of the final overlapping community. The algorithm can not only detect the overlapping communities, but also detect the isolated nodes. The effectiveness of the proposed algorithm is tested through comparing it with two existing overlapping community detection algorithms, CMP and LFM, on the Lancichinetti synthetic network and real network datasets. Results show that the size of network and size of communities have little effect on accuracy of detecting communities, and the main factor to affect the accuracy is the mixed degree among communities. The detection accuracy of the CDHC on social networks with small communities is higher than that of LFM, and it is better than CMP on networks with large communities. The CDHC algorithm improves the detection accuracy while its stability is good. Therefore, it can be concluded that the CDHC is an effective overlapping community detection algorithm for social networks. ©, 2015, Xi'an Jiaotong University. All right reserved.

引用

页码：6 / 13

页数：7

共 18 条

[1] Girvan M., Newman M.E.J., Community structure in social and biological networks, Proceedings of National Academy of Science, 9, 12, pp. 7821-7826, (2002)
[2] Tyler J.R., Wilkinson D.M., Huberman B.A., Email as spectroscopy: automated discovery of community structure within organizations, Proceedings of First International Conference on Communities and Technologies, pp. 81-96, (2003)
[3] Radicchi F., Castellano C., Cecconi F., Et al., Defining and identifying communities in networks, Proceedings of National Academy of Science, 101, 9, pp. 2658-2663, (2004)
[4] Newman M.E.J., Girvan M., Finding and evaluating community structure in networks, Physical Review: E, 69, 2, (2004)
[5] Newman M.E.J., Modularity and community structure in networks, Proceedings of National Academy of Science, 103, 23, pp. 8577-8582, (2006)
[6] Lee J., Gross S.P., Lee J., Modularity optimization by conformational space annealing, Physical Review: E, 85, 5, (2012)
[7] Shang R., Bai J., Jiao L., Et al., Community detection based on modularity and an improved genetic algorithm, Physica: A Statistical Mechanics and Its Applications, 392, 5, pp. 1215-1231, (2013)
[8] Raghavan U.N., Albert R., Kumara S., Near linear-time algorithm to detect community structures in large-scale networks, Physical Review: E, 76, 3, (2007)
[9] Subelj L., Bajec M., Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction, Physical Review: E, 83, 3, (2011)
[10] Deng X., Wang B., Wu B., Et al., Modularity modeling and evaluation in community detecting of complex network based on information entropy, Journal of Computer Research and Development, 9, 4, pp. 725-734, (2012)

← 1 2 →