JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (9): 59-68.doi: 10.6040/j.issn.1671-9352.5.2016.063

Previous Articles     Next Articles

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)

554

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

CLC Number: 

  • 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] ZHANG Jun, LI Jing-fei, ZHANG Rui, RUAN Xing-mao, ZHANG Shuo. Community detection algorithm based on effective resistance of network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(3): 24-29.
[2] ZHANG Zhong-jun, ZHANG Wen-juan, YU Lai-hang, LI Run-chuan. A community division method based on network distance and content similarity in micro-blog social network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 97-103.
[3] DENG Xiao-fang, ZHONG Yuan-sheng, L(¨overU)Lin-yuan, WANG Ming-wen, XIONG Nai-xue. Mass diffusion on coupled social networks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(3): 51-59.
[4] ZHU Sheng, ZHOU Bin, ZHU Xiang. EIP: discovering influential bloggers by user similarity and topic timeliness [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 113-120.
[5] CAI Hong-yun, MA Xiao-xue. Access control based on relationship strength for online social network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(7): 90-97.
[6] HONG Pi-zheng, LIU Shi-rong, YU Hao-long, HAO Jian. Effects of simulated nitrogen deposition on soil microbial biomass and community structure in a young plantation of Castanopsis hystrix [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(5): 18-28.
[7] ZHANG Shao-qun, WEI Jing-jing, LIAO Xiang-wen, JIAN Si-yuan, CHEN Guo-long. Emotional contagion in Twitter [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(1): 71-76.
[8] LIU Jing-lian, WANG Da-ling, ZHAO Wei-ji, FENG Shi, ZHANG Yi-fei. A community mining algorithm based on core nodes expansion [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(1): 106-114.
[9] LIU Qi, GE Lian-sheng, QIN Feng-lin. Modeling of community structure based on P2P streaming systems [J]. J4, 2012, 47(5): 84-88.
[10] LI Qi1,2, MA Jun1,2*. Person′s name disambiguation based on person  related social communities [J]. J4, 2012, 47(3): 33-37.
[11] WANG Fang, GUO Hua-Ping, NIU Chang-Yong, FAN Ming. New email community clustering method based on EVS similarity   [J]. J4, 2010, 45(3): 34-40.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd