您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2017, Vol. 52 ›› Issue (9): 59-68.doi: 10.6040/j.issn.1671-9352.5.2016.063

• • 上一篇    下一篇

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

随云仙1,刘勇1,2*   

  1. 1.黑龙江大学计算机科学技术学院, 黑龙江 哈尔滨 150080;2.黑龙江大学数据库与并行计算重点实验室, 黑龙江 哈尔滨 150080
  • 收稿日期:2017-03-06 出版日期:2017-09-20 发布日期:2017-09-15
  • 通讯作者: 刘勇(1975— ),男,博士,副教授,研究方向为数据库、数据挖掘. E-mail:acliuyong@sina.com E-mail:suiyunxian@163.com
  • 作者简介:随云仙(1991— ),女,硕士研究生,研究方向为数据挖掘. E-mail:suiyunxian@163.com
  • 基金资助:
    黑龙江大学研究生创新科研项目重点项目(YJSCX2016-018HLJU)

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

SUI Yun-xian1, LIU Yong1,2*   

  1. 1. College of Computer Science and Technology, Heilongjiang University, Harbin 150080, Heilongjiang, China;
    2. Key Laboratory of Database and Parallel Computing of Heilongjiang University, Harbin 150080, Heilongjiang, China
  • Received:2017-03-06 Online:2017-09-20 Published:2017-09-15

PDF (PC)

544

摘要： 连接多个不同社团的节点称为结构洞节点,部分已有的结构洞节点检测方法虽然可以检测到关键节点,但存在一些不足:基于局部的测量方法忽略了网络拓扑结构;对于大规模复杂的网络来说,基于全局的测量方法可扩展性差,等等。为了高效准确地检测社会网络中具有影响力的节点,提出了一种新的结构洞度量方法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.

Key words: structural hole, community detection, social network, community structure

中图分类号: 

  • TP311
[1] BURT R S. Structural holes: the social structure of competition[M]. Harvard: Harvard University Press, 1992.
[2] HOUY N. Structural holes in social networks: a remark[J]. Journal of Economic Theory, 2009, 144(1):422-431.
[3] 刘军. 社会网络分析导论[M].北京:社会科学文献出版社,2004.
[4] 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.
[5] 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.
[6] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977: 35-41.
[7] 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.
[8] BURT R S. Reinforced structural holes[J]. Social Networks, 2015, 43:149-161.
[9] 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.
[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] WIESE I S, KURODA R T, JUNIOR D N R, et al. Using structural holes metrics from communication networks to predictt change dependencies[C] // Proceedings of CYTED-RITOS International Workshop on Groupware. Switzerland: Springer International Publishing, 2014: 294-310.
[13] AHUJA G. Collaboration networks, structural holes, and innovation: a longitudinal study[J]. Administrative Science Quarterly, 2000, 45(3):425-455.
[14] BURT R S. Structural holes and good ideas1[J]. American journal of sociology, 2004, 110(2):349-399.
[15] 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.
[16] GOYAL S, VEGA-REDONDO F. Structural holes in social networks[J]. Journal of Economic Theory, 2007, 137(1):460-492.
[17] 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.
[18] 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.
[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] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[R]. Stanford: Stanford University, 1999.
[21] BURT R S. Reinforced structural holes[J]. Social Networks, 2015, 43:149-161.
[22] GOYAL S, VEGA-REDONDO F. Structural holes in social networks[J]. Journal of Economic Theory, 2007, 137(1):460-492.
[23] 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.
[24] 苏晓萍,宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点[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.
[1] 蔡红云,马晓雪. 在线社会网络中基于关系强度的访问控制机制[J]. 山东大学学报（理学版）, 2016, 51(7): 90-97.
[2] 李琦1,2,马军1,2*. 基于人物相关社区的重名消解研究[J]. J4, 2012, 47(3): 33-37.
[3] 王芳 郭华平 牛常勇 范明. 一种基于EVS相似度的邮件社区聚类方法[J]. J4, 2010, 45(3): 34-40.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发