基于二步邻居拓扑的E-Burt结构洞检测算法

连接多个不同社团的节点称为结构洞节点,部分已有的结构洞节点检测方法虽然可以检测到关键节点,但存在一些不足:基于局部的测量方法忽略了网络拓扑结构;对于大规模复杂的网络来说,基于全局的测量方法可扩展性差,等等。为了高效准确地检测社会网络中具有影响力的节点,提出了一种新的结构洞度量方法E-Burt,用来寻找结构洞节点。该方法利用节点与其二步邻居构成的拓扑关系来计算节点的有效规模,用该结果作为结构洞节点重要性的评价指标,计算每个节点的结构洞度量值,并给出了形式化定义。E-B算法基于网络拓扑结构,每次模拟迭代将选中的结构洞节点度量值置为零,下一次迭代只计算该节点二步邻居的有效规模,大大降低了时间复杂度。最后通过实验验证了算法的时间效率,分析了算法的精确度,对算法的正确性进行了证明,并与存在的经典结构洞发现算法进行了对比。

Mining algorithm of E-burt structural hole based on two-step neighbor

There are many structural hole spanners in social network, which connected different communities. Although the existed algorithms of finding structural hole spanners are effective, but there is still some deficiencies. For example, local based algorithms ignored the structure of the networks and global algorithms procured a worse scalability on the large-scale social network. In order to detection the influential points more efficient and accurate, we proposed a new method E-Burt to find structural hole spanners which considers both the number of the neighbor and the topological of two-step neighbor as importance metrics of structural spanners and calculate the importance metrics for each node and give a formal definition. We proposed E-B algorithm based on the network topology and iteration algorithm sets the selected node importance metrics to zero and the next iteration computes the effective size of the two-step neighbor which reduces the time complexity greatly. Finally, verify the time efficiency and analyze the accuracy and prove the correctness of the algorithm and compare with the existing classical structural hole spanners finding algorithm.