|
|
- 2017
基于二步邻居拓扑的E-Burt结构洞检测算法
|
Abstract:
摘要： 连接多个不同社团的节点称为结构洞节点,部分已有的结构洞节点检测方法虽然可以检测到关键节点,但存在一些不足:基于局部的测量方法忽略了网络拓扑结构;对于大规模复杂的网络来说,基于全局的测量方法可扩展性差,等等。为了高效准确地检测社会网络中具有影响力的节点,提出了一种新的结构洞度量方法E-Burt,用来寻找结构洞节点。该方法利用节点与其二步邻居构成的拓扑关系来计算节点的有效规模,用该结果作为结构洞节点重要性的评价指标,计算每个节点的结构洞度量值,并给出了形式化定义。E-B算法基于网络拓扑结构,每次模拟迭代将选中的结构洞节点度量值置为零,下一次迭代只计算该节点二步邻居的有效规模,大大降低了时间复杂度。最后通过实验验证了算法的时间效率,分析了算法的精确度,对算法的正确性进行了证明,并与存在的经典结构洞发现算法进行了对比。
Abstract: 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
| [1] | BURT R S. Structural holes: the social structure of competition[M]. Harvard: Harvard University Press, 1992. |
| [2] | 刘军. 社会网络分析导论[M].北京:社会科学文献出版社,2004. |
| [3] | AHUJA G. Collaboration networks, structural holes, and innovation: a longitudinal study[J]. Administrative Science Quarterly, 2000, 45(3):425-455. |
| [4] | BURT R S. Secondhand brokerage: evidence on the importance of local structure for managers, bankers, and analysts[J]. Academy of Management Journal, 2007, 50(1):119-148. |
| [5] | NISBET M C, KOTCHER J E. A two-step flow of influence? opinion-leader campaigns on climate change[J]. Science Communication, 2009, 30(3):328-354. |
| [6] | WIESE I S, KURODA R T, JUNIOR D N R, et al. Using structural holes metrics from communication networks to predictt change dependencies[C] // Proceedings of CYTED-RITOS International Workshop on Groupware. Switzerland: Springer International Publishing, 2014: 294-310. |
| [7] | REZVANI M, LIANG W, XU W, et al. Identifying top-k structural hole spanners in large-scale social networks[C] // Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York: ACM, 2015: 263-272. |
| [8] | FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977: 35-41. |
| [9] | HOUY N. Structural holes in social networks: a remark[J]. Journal of Economic Theory, 2009, 144(1):422-431. |
| [10] | BHOWMIK T, NIU N, SINGHANIA P, et al. On the role of structural holes in requirements identification: an exploratory study on open-source software development[J]. ACM Transactions on Management Information Systems(TMIS), 2015, 6(3):10. |
| [11] | XIANG M, LIU W, BAI Q, et al. Simmelian ties and structural holes: exploring their topological roles in forming trust for securing wireless sensor networks[C] // Proceedings of 2015 IEEE Trustcom/BigDataSE/ISPA. Los Alamitos: IEEE Computer Society, 2015: 96-103. |
| [12] | BURT R S. Structural holes and good ideas1[J]. American journal of sociology, 2004, 110(2):349-399. |
| [13] | ZHANG E, WANG G, GAO K, et al. Generalized structural holes finding algorithm by bisection in social communities[C] // Proceedings of the 6th International Conference on Genetic and Evolutionary Computing(ICGEC). New York: IEEE, 2012: 276-279. |
| [14] | SU X P, SONG Y R. Using neighborhood “structure hole” to find the most influential nodes in social networks[J]. Acta Phys Sin, 2015, 64(2):1-11. |
| [15] | PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[R]. Stanford: Stanford University, 1999. |
| [16] | LOU T, TANG J. Mining structural hole spanners through information diffusion in social networks[C] // Proceedings of the 22nd International Conference on World Wide Web. New York: ACM, 2013: 825-836. |
| [17] | BURT R S. Reinforced structural holes[J]. Social Networks, 2015, 43:149-161. |
| [18] | XIA S, DAI B T, LIM E P, et al. Link prediction for bipartite social networks: the role of structural holes[C] // Proceedings of 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining(ASONAM). New York: IEEE, 2012: 153-157. |
| [19] | BHOWMIK T, NIU N, SINGHANIA P, et al. On the role of structural holes in requirements identification: an exploratory study on open-source software development[J]. ACM Transactions on Management Information Systems(TMIS), 2015, 6(3):10. |
| [20] | GOYAL S, VEGA-REDONDO F. Structural holes in social networks[J]. Journal of Economic Theory, 2007, 137(1):460-492. |
| [21] | GOYAL S, VEGA-REDONDO F. Structural holes in social networks[J]. Journal of Economic Theory, 2007, 137(1):460-492. |
| [22] | 苏晓萍,宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点[J].物理学报,2015, 64(2):1-11. SU Xiaoping, SONG Yurong.Leveraging neighborhood “structural holes” to identifying key spreaders in so cial networks[J.] Acta Physica Sinica, 2015, 64(2):1-11. |
| [23] | FREEMAN L C, BORGATTI S P, WHITE D R. Centrality in valued graphs: a measure of betweenness based on network flow[J]. Social networks, 1991, 13(2):141-154. |
| [24] | BURT R S. Reinforced structural holes[J]. Social Networks, 2015, 43:149-161. |
