一种基于效用的社区发现算法
A Community Discovery Algorithm Based on Utility

作者: 杨德品 , 周丽华 , 程 超 , 龙克珍 :云南大学信息学院计算机科学与工程系,昆明;

关键词: 社会网络社区发现效用K均值Social Network Community Discovery Utility K-Means

摘要:
本文从图论思想出发,提出了一种基于效用的社区发现算法,该方法既考虑了社区成员联系的频繁度又考虑了联系的重要度。本文定义了效用的概念,通过效用来描述节点相似度,并实现了基于效用的社区发现(Community Discovery Based on Utility,简写为CDBU)算法,该算法有效地避免了传统的基于联系频繁度的社区发现方法忽略了联系重要度的弊端。最后,本文在真实数据集上进行了实验,验证了所提出算法的合理性和有效性。

Abstract:
Based on the graph theory, this paper proposes a community discovery algorithm based on utility. The method considers not only the contact frequency but also the importance of the links between community members. The paper defines the concept of utility to describe nodes similarity and implements the CDBU algorithm. The algorithm proposed effectively avoids the abuse of the traditional community discovery method based on the contact frequency, which neglects the important degree of contact. Finally, on the real-world dataset, we verify the rationality and validity of the algorithm proposed in this paper.

文章引用: 杨德品 , 周丽华 , 程 超 , 龙克珍 (2014) 一种基于效用的社区发现算法。 运筹与模糊学, 4, 15-23. doi: 10.12677/ORF.2014.41003

参考文献

[1] Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of small-world networks. Nature, 393, 440-442.

[2] Barabási, A.L. and Albert, R. (1999) Emergence of scaling in random networks. Science, 286, 509-512.

[3] Albert, R., Barabási, A.L. and Jeong, H. (2000) The Internet’S Achilles heel: Error and attack tolerance of complex networks. Nature, 406, 378-382.

[4] Barabási, A.L., Albert, R., Jeong, H. and Bianconi, G. (2000) Power-law distribution of the World Wide Web. Science, 287, 2115a.

[5] Girvan, M. and Newman, M.E.J. (2002) Community structure in social and biological networks. Proceedings of the National Academy of Science, 9, 7821-7826.

[6] Newman, M.E.J. and Girvan, M. (2004) Finding and evaluating community structure in networks. Physical Review E, 69, Article ID: 026113.

[7] Kleinberg, J.M. (1999) Authoritative sources in a hyperlinked environment. Journal of the ACM, 46, 604-632.

[8] Palla, G., Derenyi, I., Farkas, I. and Vicsek, T. (2005) Uncovering the overlapping community structures of complex networks in nature and society. Nature, 435, 814-818.

[9] Barabási, A.L. and Oltvai, Z.N. (2004) Network biology: Understanding the cell’s functional organization. Nature Reviews Genetics, 11, 101- 113.

[10] Yang, B., Liu, D.Y., Liu, J.M., Jin, D. and Ma, H.B. (2009) Complex network clustering algorithms. Journal of Software, 20, 54-66 (in Chinese with English Abstract). http://www.jos.org.cn/1000-9825/3464.htm

[11] 淦文燕, 赫南, 李德毅, 王建民 (2009) 一种基于拓扑势的网络社区发现方法. 软件学报, 8, 2241-2254.

[12] 吴文涛, 肖仰华, 何震瀛, 汪卫, 余韬 (2009) 基于权重信息挖掘社会网络中的隐含社团. 计算机研究与发展, ISSN 1000-1239/CN 11- 1777/TP46, 540-546.

[13] 孔兵 (2012) 基于连接度量的社区发现研究. 博士学位论文, 云南大学, 昆明.

[14] Yin, J.F., Zheng, Z.G. and Cao, L.B. (2012) USpan: An efficient algorithm for mining high utility sequential patterns. KDD’12, Beijing, 12-16 August 2012, 660-668.

[15] 熊学栋 (2007) 数据库中关联规则及效用模式挖掘算法研究. 硕士学位论文, 湘潭大学, 湘潭.

[16] 林旺群, 卢风顺, 丁兆云, 吴泉源, 周斌, 贾焰 (2012) 基于带权图的层次化社区并行计算方法. 软件学报, 6, 1517-1530.

[17] 王实 (2002) 数据挖掘中的聚类算法. 计算机科学, 4, 42-45.

[18] 孙孝萍 (2002) 基于聚类分析的数据挖掘算法研究. 硕士生论文.

分享
Top