基于重叠社区和结构洞度的社会网络结构洞识别算法

A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree

结构洞是社会网络中的关键位置,对信息扩散起中介作用。为高效、准确地辨识具有社团结构的社会网络中占据结构洞的节点,提出了一种基于重叠社区和结构洞度的结构洞识别算法,旨在找到一组最具信息优势和控制优势的节点。基本思想是首先定位社区之间的重叠节点,然后利用节点的邻接差异和连接的社区差异衡量其非冗余性,计算出重叠节点的结构洞度,通过对结构洞度值升序排列发现占据结构洞的节点集。应用于实际数据集的实验结果表明,与网络约束系数算法、中介中心度算法、MaxD算法相比,该算法的识别准确度最高,时间复杂度最低。

Structural holes take up key positions in social networks, and they play an mtermealary role in information diffusion. To efficiently and accurately identify nodes which occupy structural holes in social networks with community structure, we propose a structural hole identification algorithm based on overlapping communities and structural hole degree. We attempt to find a set of nodes which possess the most information superiority and control superiority. The basic idea is to locate the overlapping nodes between communities in the first place, and then calculate the structural hole degree of overlap- ping nodes by measuring the non-redundancy degree through an integration of adjacent differences and community connection differences. A set of structural holes can be finally found out according to the as- cending order of nodes＂ structural hole degree. Experiments on real datasets show that the proposed al- gorithm has the best identification accuracy and the lowest time complexity in comparison with the net- work constraint index algorithm, the betweenness centrality algorithm and the MaxD algorithm.