基于标签传播的语义重叠社区发现算法  

An Overlapping Semantic Community Structure Detecting Algorithm by Label Propagation

作　　者：辛宇[1] 杨静[1] 谢志强[2] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《自动化学报》2014年第10期2262-2275,共14页Acta Automatica Sinica

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

摘　　要：语义社会网络(Semantic social network,SSN)是一种由信息节点及链接关系构成的新型复杂网络,为此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题.由此提出标签传播的语义重叠社区发现算法,该算法以标签传播算法(Latent Dirichlet allocation,LDA)模型为语义信息模型,利用Gibbs取样法建立节点语义信息到语义空间的量化映射;提出可度量节点间相似性的主成分(Semantic coherent neighborhood propinquity,SCNP)模型和语义影响力(Semantic impact,SI)模型;以SCNP作为标签传播的权重,以SI作为截断值的参数,提出一种改进的Semantic-LPA(Semantic label propagation algorithm)算法;提出可度量语义社区发现结果的语义模块度模型,并通过实验分析,验证了算法及语义模块度模型的有效性及可行性.Since the semantic social network （SSN） is a new kind of complex networks consisting of information nodes and link relationships, the traditional community detection algorithms which depend on the adjacency in social networks are not efficient in the SSN. To solve this problem, an overlapping community structure detecting method in semantic social network is proposed based on label propagation. Firstly, the algorithm utilizes the Gibss sampling method to establish the quantization mapping by which semantic information in nodes can be mapped into the semantic space, with the latent Dirichlet allocation （LDA） as the semantic model. Secondly, a principal component SCNP model is proposed which could measure the propinquity between nodes and the semantic impact model. Thirdly, an improved semantic label propagation algorithm is put forward, with SCNP as the weight of propagation and SI as the parameter of threshold. Finally, a semantic model by which the community structure of SSN can be measured is presented. The efficiency and feasibility of the algorithm and the semantic modularity are verified by experimental analysis.

关 键 词：语义社会网络 重叠社区 LDA模型 标签传播算法 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]