一种面向语义重叠社区发现的 Block 场取样算法

辛宇; 杨静; 谢志强

doi:10.16383/j.aas.2015.c140136

一种面向语义重叠社区发现的 Block 场取样算法

doi: 10.16383/j.aas.2015.c140136

辛宇¹,
杨静^1, ,,
谢志强²

1.
哈尔滨工程大学计算机科学与技术学院哈尔滨 150001;
2.
哈尔滨理工大学计算机科学与技术学院哈尔滨 150080

基金项目:

国家自然科学基金(61370083,61073043,61073041,61370086),国家教育部博士点基金(20112304110011,20122304110012)资助

详细信息

作者简介:
辛宇哈尔滨工程大学计算机科学与技术学院博士研究生. 2011 年获哈尔滨理工大学计算机科学与技术学院硕士学位. 主要研究方向为数据库与知识工程.E-mail: xinyu@hrbeu.edu.cn

通讯作者:
杨静哈尔滨工程大学计算机科学与技术学院教授. 主要研究方向为数据库与知识工程. 本文通信作者.E-mail: yangjing@hrbeu.edu.cn

计量
- 文章访问数: 1643
- HTML全文浏览量: 34
- PDF下载量: 787
- 被引次数: 0
出版历程
- 收稿日期: 2014-03-14
- 修回日期: 2014-08-12
- 刊出日期: 2015-02-20

An Overlapping Community Structure Detecting Algorithm in Semantic Social Network Based on Block Field

1.
College of Computer Science and Technology, Harbin Engineering University, Harbin 150001;
2.
College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080

Funds:

Supported by National Natural Science Foundation of China (61370083, 61073043, 61073041, 61370086) and National Research Foundation for the Doctoral Program of Higher Education of China (20112304110011, 20122304110012)

摘要

摘要: 语义社会网络(Semantic social network, SSN)是一种包含信息节点及社会关系构成的新型复杂网络. 传统语义社会网络分析算法在进行社区挖掘时, 需要预先设定社区个数且无法发现重叠社区. 针对这一问题, 提出一种面向语义重叠社区发现的block场采样算法, 该算法首先以LDA (Latent dirichlet allocation)模型为语义分析模型, 建立了以取样节点为核心节点的block 场BAT (Block-author-topic)模型; 其次, 根据节点的语义分析结果, 建立可度量block区域的语义凝聚力方法, 实现了语义信息的可度量化; 最后, 以节点的语义凝聚力为输入, 改进了重叠社区发现的标签传播算法(Label propagation algorithm, LPA)及可评价语义社区的SQ度量模型, 并通过实验分析, 验证了本文算法及SQ 度量模型的有效性及可行性.
- 语义社会网络 /
- 重叠社区 /
- LDA模型 /
- 社区发现
Abstract: The semantic social network (SSN) is a new kind of complex networks consisting of the node content and topological relationship. The traditional community detection algorithms need to preset the number of the communities and could not detect the overlapping communities. To solve this problem, an overlapping community structure detecting algorithm in semantic social network based on the block field is proposed. Firstly, it takes the latent dirichlet allocation (LDA) model as the semantic analyzing model, establishing the block-author-topic (BAT) model with the sampling node as the core node. Secondly, it suggests the measurement of the semantic cohesion of the block field, depending on the analysis of SSN, to achieve the evaluation of semantic information. Finally, it improves the label propagation algorithm (LPA) which could detect the overlapping communities, with the semantic cohesion as input, and designs the SQ measurement modularity for semantic measuring. The efficiency and feasibility of the algorithm and the semantic modularity are verified via experimental analysis.
- Semantic social network /
- overlapping community /
- latent dirichlet allocation (LDA) /
- community detection

HTML全文

参考文献(32)

[1]	Yang Bo, Liu Da-You, Liu Jinming, Jin Di, Ma Hai-Bin. Complex network clustering algorithms. Journal of Software, 2009, 20(1): 54-66(杨博, 刘大有, Liu Jinming, 金弟, 马海宾. 复杂网络聚类方法. 软件学报, 2009, 20(1): 54-66)
[2]	[2] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of National Academy of Science of the United States of America, 2002, 99(12): 7821-7826
[3]	[3] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066133
[4]	[4] Palla G, Derenyi I, Farkas I, Vicsde T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818
[5]	[5] Shen H W, Cheng X Q, Cai K, Hu M B. Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and Its Applications, 2009, 388(8): 1706-1712
[6]	[6] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks.New Journal of Physics, 2009, 11(3): 033015-27
[7]	[7] Gregory S. Finding overlapping communities in networks by label propagation. New Journal of Physics, 2010, 12(10): 103018
[8]	[8] Jin D, Yang B, Baquero C, Liu D Y, He D X, Liu J. A Markov random walk under constraint for discovering overlapping communities in complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2011, 2011(5): P05031-21
[9]	Jin Di, Yang Bo, Liu Jie, Liu Da-You, He Dong-Xiao. Ant colony optimization based on random walk for community detection in complex networks. Journal of Software, 2012, 23(3): 451-464(金弟, 杨博, 刘杰, 刘大有, 何东晓. 复杂网络簇结构探测 --- 基于随机游走的蚁群算法. 软件学报, 2012, 23(3): 451-464)
[10]	Gan Wen-Yan, He Nan, Li De-Yi, Wang Jian-Min. Community discovery method in networks based on topological potential. Journal of Software, 2009, 20(8): 2241-2254(淦文燕, 赫南, 李德毅, 王建民. 一种基于拓扑势的网络社区发现方法, 软件学报, 2009, 20(8): 2241-2254)
[11]	Jin Di, Liu Jie, Yang Bo, He Dong-Xiao, Liu Da-You. Genetic algorithm with local search for community detection in large-scale complex networks. Acta Automatica Sinica, 2011, 37(7): 873-882(金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882)
[12]	He Dong-Xiao, Zhou Xu, Wang Zuo, Zhou Chun-Guang, Wang Zhe, Jin Di. Community mining in complex Networks-Clustering combination based genetic algorithm. Acta Automatica Sinica, 2010, 36(8): 1160-1170(何东晓, 周栩, 王佐, 周春光, 王喆, 金弟. 复杂网络社区挖掘基于聚类融合的遗传算法. 自动化学报, 2010, 36(8): 1160-1170)
[13]	Yang Bo, Liu Jie, Liu Da-You. A random network ensemble model based generalized network community mining algorithm. Acta Automatica Sinica, 2012, 38(5): 812-822(杨博, 刘杰, 刘大有. 基于随机网络集成模型的广义网络社区挖掘算法. 自动化学报, 2012, 38(5): 812-822)
[14]	Blei D M, Ng A Y, Jordan M I. Latent dirichlet allocation. Journal of Machine Learning Research, 2003, 3: 993-1022
[15]	Zhang H Z, Qiu B J, Giles C L, Foley H C, Yen J. An LDA-based community structure discovery approach for large-scale social networks. In: Proceedings of the 2007 IEEE on Intelligence and Security Informatics. New Brunswick, NJ: IEEE, 2007. 200-207
[16]	Kemp C, Tenenbaum J B, Griffiths T L, Yamada T, Ueda N. Learning systems of concepts with an infinite relational model. In: Proceedings of the 21st National Conference on Artificial Intelligence. California: AAAI Press 2006. 381- 388
[17]	Henderson K, Eliassi R T. Applying latent dirichlet allocation to group discovery in large graphs. In:　Proceedings of the 2009 ACM Symposium on Applied Computing. Honolulu, Hawaii, USA: ACM, 2009. 1456-1461
[18]	Henderson K, Eliassi R T, Papadimitriou S, Faloutsos C. HCDF: A hybrid community discovery framework. In: Proceedings of the 2010 SIAM Conference. SDM. 2010. 754-765
[19]	Zhang H Z, Giles C L, Foley H C, Yen J. Probabilistic community discovery using hierarchical latent Gaussian mixture model. In: Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada: AAAI, 2007. 663 -668
[20]	Zhang H Z, Li W, Wang X R, Giles C L, Foley H C, Yen J. HSN-PAM: finding hierarchical probabilistic groups from large-scale networks. In: Proceedings of the 7th IEEE International Conference on Data Mining Workshops. Omaha, Nebraska, USA: IEEE, 2007. 27-32
[21]	Steyvers M, Smyth P, Rosen Z M, Griffiths T. Probabilistic author-topic models for information discovery. In: Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2004. 306-315
[22]	McCallum A, Corrada-Emmanuel A, Wang X. Topic and role discovery in social networks. Computer Science Department Faculty Publication Series, 2005, 3(1): 1-7
[23]	McCallum A, Wang X R, Corrada-Emmanuel A. Topic and role discovery in social networks with experiments on Enron and academic email. Journal of Artificial Intelligence Research, 2007, 30(1): 249-272
[24]	Zhou D, Manavoglu E, Li J, Giles C L, Zha H Y. Probabilistic models for discovering e-communities. In: Proceedings of the 15th International Conference on World Wide Web. Edinburgh, Scotland, UK: ACM, 2006. 173-182
[25]	Cha Y, Cho J. Social-network analysis using topic models. In: Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM, 2012. 565-574
[26]	Wang X, Mohanty N, McCallum A. Group and topic discovery from relations and text. In: Proceedings of the 3rd International Workshop on Link Discovery. New York, USA: ACM, 2005. 28-35
[27]	Pathak N, DeLong C, Banerjee A, Erickson K. Social topic models for community extraction. In: Proceedings of the 2nd SNA-KDD Workshop. Las Vegas, Nevada, USA: ACM, 2008. 1-10
[28]	Mei Q Z, Cai D, Zhang D, Zhai C X. Topic modeling with network regularization. In: Proceedings of the 17th International Conference on World Wide Web. Beijing, China: ACM, 2008. 101-110
[29]	Sachan M, Contractor D, Faruquie T A, Subramaniam V. Probabilistic model for discovering topic based communities in social networks. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2011. 2349-2352
[30]	Sachan M, Contractor D, Faruquie T A, Subramaniam V L. Using content and interactions for discovering communities in social networks. In: Proceedings of the 21st International Conference on World Wide Web. New York, USA: ACM, 2012. 331-340
[31]	Yin Z J, Cao L L, Gu Q Q, Han J W. Latent community topic analysis: integration of community discovery with topic modeling. ACM Transactions on Intelligent Systems and Technology, 2012, 3(4): 63
[32]	Xie J R, Szymanski B K, Liu X M. SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: Proceedings of the 11th IEEE International Conference of Data Mining Workshops. Vancouver, BC: IEEE, 2011. 344-349

施引文献

资源附件(0)

访问统计

点击查看大图

计量

文章访问数: 1643
HTML全文浏览量: 34
PDF下载量: 787
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

一种面向语义重叠社区发现的 Block 场取样算法

doi: 10.16383/j.aas.2015.c140136

作者简介:
辛宇哈尔滨工程大学计算机科学与技术学院博士研究生. 2011 年获哈尔滨理工大学计算机科学与技术学院硕士学位. 主要研究方向为数据库与知识工程.E-mail: xinyu@hrbeu.edu.cn

通讯作者:
杨静哈尔滨工程大学计算机科学与技术学院教授. 主要研究方向为数据库与知识工程. 本文通信作者.E-mail: yangjing@hrbeu.edu.cn

计量

An Overlapping Community Structure Detecting Algorithm in Semantic Social Network Based on Block Field

计量

目录

留言板

一种面向语义重叠社区发现的 Block 场取样算法

doi: 10.16383/j.aas.2015.c140136

作者简介: 辛宇 哈尔滨工程大学计算机科学与技术学院博士研究生. 2011 年获哈尔滨理工大学计算机科学与技术学院硕士学位. 主要研究方向为数据库与知识工程.E-mail: xinyu@hrbeu.edu.cn

通讯作者: 杨静 哈尔滨工程大学计算机科学与技术学院教授. 主要研究方向为数据库与知识工程. 本文通信作者.E-mail: yangjing@hrbeu.edu.cn

计量

出版历程

An Overlapping Community Structure Detecting Algorithm in Semantic Social Network Based on Block Field

计量

出版历程

目录

作者简介:
辛宇哈尔滨工程大学计算机科学与技术学院博士研究生. 2011 年获哈尔滨理工大学计算机科学与技术学院硕士学位. 主要研究方向为数据库与知识工程.E-mail: xinyu@hrbeu.edu.cn

通讯作者:
杨静哈尔滨工程大学计算机科学与技术学院教授. 主要研究方向为数据库与知识工程. 本文通信作者.E-mail: yangjing@hrbeu.edu.cn