A Study of Identifying Structural Hole Spanners in Large Scale Networs

  • Authors

    • K. Shruthi
    • Dr. Y. Sri Lalitha
    https://doi.org/10.14419/ijet.v7i3.24.24564
  • Filter Techniques, Lower upper bound estimation, all pairs shortest paths, top-k structural hole, social network

  • Abstract

    The expansion of internet and increasingly evolving Social Network Sites (SNS) has facilitated internet-users to access a common stage for communication.  With the increase in communications between a group of internet-users or between a pair of individuals, keeping track of their interactions is becoming a complex task.  Social Networks datasets contain valuable information that can be examined to extract useful patterns.  Social Network Analysis (SNA) is a study of patterns and relations in data.  This involves identifying Communities or sub-communities from a large network of nodes.  The individuals or entities in such Networks are partitioned into closely connected groups called Communities.    There can be network structures that connect two or more communities.  The Individuals that connect communities in such networks are termed as Structural Hole Spanners (SHS).  Closely related communities and Structural Hole Spanners play an important role in various business applications.  Therefore the study of identifying the dense communities and highly qualified structural holes in a large network of nodes has become study of interest among researchers.   The evolution of Big Data Analytics is making it feasible. This paper studies the techniques of community detection and structural holes identification in literature.  It made a preliminary study on SHS and presented two popular Structural Holes Identification Methods with their results.

     

     

  • References

    1. [1] James, Paul (2006). Gloabalism, Nationalism, Tribalism:Bringing Theory Back In--Volume 2 of Towards a Theory of Abstract Community. London:Sage Publications.

      [2] Punam Bedi, Chavvi Sharma,â€Community Detection in Social Networksâ€, in : Data Mining and Knowledge Discovery · February 2016.

      [3] Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. Bell system technical journal 1970, 49(2):291-307.

      [4] Newman M. Community detection and graph partitioning. EPL (Europhysics Letters) 2013, 103 (2):28003. doi:10.1209/0295-5075/103/28003.

      [5] Rattigan MJ, Maier M, Jensen D. Graph clustering with network structure indices. In: Proceedings of the 24th International conference on Machine learning(ICML): ACM; 2007 : 783790.doi:10.1145/1273496.1273595.

      [6] Chen J, Yuan B. Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics 2006, 22 (18):2283-2290. doi:10.1093/bioinformatics/btl370.

      [7] Holme P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways. Bioinformatics 2003, 19 (4):532-538.

      [8] Pinney JW, Westhead DR. Betweenness-based decomposition methods for social and biological networks. Interdisciplinary Statistics and Bioinformatics 2006:87-90.

      [9] Gregory S. An algorithm to find overlapping community structure in networks. In: Knowledge discovery in databases: PKDD Springer; 2007, 91-102.doi:10.1007/978-3-540-74976-9_12.

      [10] Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A. Self-similar community structure in a network of human interactions. Physical review E 2003, 68 (6):065103. doi:10.1103/PhysRevE.68.065103.

      [11] Arenas A, Danon L, Diaz-Guilera A, Gleiser PM, Guimera R. Community analysis in social networks. The European Physical Journal B-Condensed Matter and Complex Systems 2004, 38 (2):373-380. doi:10.1140/epjb/e2004-00130-1.

      [12] Tyler JR, Wilkinson DM, Huberman BA. E-mail as spectroscopy: Automated discovery of community structure within organizations. The Information Society 2005, 21 (2):143-153.

      [13] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America 2004, 101 (9):2658-2663. doi:10.1073/pnas.0400054101.

      [14] Moon S, Lee J-G, Kang M, Choy M, Lee J-w. Parallel community detection on large graphs with MapReduce and GraphChi. Data & Knowledge Engineering 2015, Article in Press. doi:10.1016/j.datak.2015.05.001.

      [15] Clauset A, Newman ME, Moore C. Finding community structure in very large networks. Physical review E 2004, 70 (6):066111. doi:10.1103/PhysRevE.70.066111.

      [16] Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008. doi:10.1088/17425468/2008/10/P10008.

      [17] Guimera R, Sales-Pardo M, Amaral LAN. Modularity from fluctuations in random graphs and complex networks. Physical Review E 2004, 70 (2):025101. doi:10.1103/PhysRevE.70.025101.

      [18] Zhou Z, Wang W, Wang L. Community Detection Based on an Improved Modularity. Pattern Recognition 2012:638-645. doi:10.1007/978-3-642-33506-8_78.

      [19] Duch J, Arenas A. Community detection in complex networks using extremal optimization. Physical review E 2005, 72 (2):027104. doi:10.1103/PhysRevE.72.027104.

      [20] Ye Z, Hu S, Yu J. Adaptive clustering algorithm for community detection in complex networks. Physical Review E 2008, 78 (4):046115. doi:10.1103/PhysRevE.78.046115.

      [21] Wahl S, Sheppard J. Hierarchical Fuzzy Spectral Clustering in Social Networks Using Spectral Characterization. In: The Twenty-Eighth International Flairs Conference; 2015 : 305-310

      [22] Falkowski T, Barth A, Spiliopoulou M. DENGRAPH: A density-based community detection algorithm. In: IEEE/WIC/ACM International Conference on Web Intelligence (WI); 2007: 112115.doi:10.1109/WI.2007.74.

      [23] Dongen SV. Graph Clustering by Flow Simulation, PhD thesis, University of Utrecht. 2000.

      [24] Nikolaev AG, Razib R, Kucheriya A. On efficient use of entropy centrality for social network analysis and community detection. Social Networks 2015, 40:154-162. doi:10.1016/ j.socnet.2014.10.002.

      [25] Steinhaeuser K, Chawla NV. Identifying and evaluating community structure in complex networks. Pattern Recognition Letters 2010, 31 (5):413-421. doi:10.1016/j.patrec.2009.11.001.

      [26] Pizzuti C. GA-Net: A genetic algorithm for community detection in social networks. In: Parallel Problem Solving from Nature–PPSN X: Springer; 2008, 1081-1090.doi:10.1007/978-3-54087700-4_107.

      [27] Pizzuti C. A multiobjective genetic algorithm to find communities in complex networks. IEEE Transactions on Evolutionary Computation 2012, 16 (3):418-430. doi:10.1109/TEVC.2011.2161090.

      [28] Hafez AI, Ghali NI, Hassanien AE, Fahmy AA. Genetic algorithms for community detection in social networks. In: 12th International Conference on Intelligent Systems Design and Applications (ISDA): IEEE; 2012 : 460-465.doi:10.1109/ISDA.2012.6416582.

      [29] Mazur P, Zmarzlowski K, Orlowski AJ. A Genetic Algorithms Approach to Community Detection. Acta Physica Polonica Series A- General Physics 2010, 117(4).

      [30] Liu X, Li D, Wang S, Tao Z. Effective algorithm for detecting community structure in complex networks based on GA and clustering. In: International Conference on Computational Science (ICCS 07): Springer; 2007:657-664.

      [31] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms. arXiv preprint arXiv: 0711.0491 2007.

      [32] Zadeh PM, Kobti Z. A Multi-Population Cultural Algorithm for Community Detection in Social Networks. Procedia Computer Science 2015, 52:342-349. doi:10.1016/j.procs.2015.05.105.

      [33] Raghavan UN, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 2007, 76 (3):036106. doi:10.1103/PhysRevE.76.036106.

      [34] Wu Z-H, Lin Y-F, Gregory S, Wan H-Y, Tian S-F. Balanced multi-label propagation for overlapping community detection in social networks. Journal of Computer Science and Technology 2012, 27(3):468-479.

      [35] Xie J, Chen M, Szymanski BK. LabelrankT: Incremental community detection in dynamic networks via label propagation. In: Proceedings of the Workshop on Dynamic Networks Management and Mining: ACM; 2013:25-32.

      [36] Girvan M, Newman M. Community structure in social and biological networks. Proceedings of the national academy of sciences 2002, 99 (12):7821-7826. doi:10.1073/pnas.122653799.

      [37] Blei DM, Ng AY, Jordan MI. Latent dirichlet allocation. the Journal of machine Learning research 2003, 3:993-1022.

      [38] Xin Y, Yang J, Xie Z-Q. A semantic overlapping community detection algorithm based on field sampling. Expert Systems with Applications 2015, 42 (1)

      [39] Xia Z, Bu Z. Community detection based on a semantic network. Knowledge-Based Systems 2012, 26. doi:10.1016/j.knosys.2011.06.014.

      [40] Zhao Z, Feng S, Wang Q, Huang JZ, Williams GJ, Fan J. Topic oriented community detection through social objects and link analysis in social networks. Knowledge-Based Systems 2012, 26:164-173. doi:10.1016/j.knosys.2011.07.017.

      [41] Deerwester SC, Dumais ST, Landauer TK, Furnas GW, Harshman RA. Indexing by latent semantic analysis. JAsIs 1990, 41 (6):391-407.

      [42] Nguyen T, Phung D, Adams B, Tran T, Venkatesh S. Hyper-community detection in the blogosphere. In: Proceedings of second ACM SIGMM workshop on Social media: ACM; 2010.

      [43] Natarajan N, Sen P, Chaoji V. Community detection in content-sharing social networks. In: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining: ACM; 2013.doi:10.1145/2492517.2492546.

      [44] KELLEY, S., GOLDBERG, M., MAGDON-ISMAIL, M., MERTSALOV, K.,AND WALLACE, A. 2011. Deï¬ning and discovering communities in social networks. In Handbook of Optimization in Complex Networks, Springer, 139–168.

      [45] REID, F., MCDAID, A. F.,AND HURLEY, N. J. 2011. Partitioning breaks communities. In Proceedings of the International Conference on Advances in Social Networks Analysis and Mining(ASONAM’11). 102–109.

      [46] FARKAS, I., ABEL, D., PALLA, G.,AND VICSEK, T. 2007. Weighted network modules. New J. Phys. 9, 6, 180.

      [47] AHN, Y.-Y., BAGROW, J. P.,AND LEHMANN, S. 2010. Link communities reveal multiscale complexity in networks. Nature 466, 761–764.

      [48] GREGORY, S. 2010. Finding overlapping communities in networks by label propagation. New J. Phys. 12, 10.

      [49] LANCICHINETTI,A.,FORTUNATO,S,AND KERTESZ, J.2009. Detecting the overlapping and hierarchical community structure of complex networks. New J. Phys. 11, 3.

      [50] RAGHAVAN,U.N.,ALBERT,R.,AND KUMARA,S.2007.Near line artime algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 3.

      [51] XIE, J.AND SZYMANSKI, B. K. 2011. Community detection using a neighborhood strength driven label propagation algorithm. In Proceedings of the IEEE Network Science Workshop (NSW’11). 188–195.

      [52] R. S. Burt, Structural holes: The social structure of competition. Harvard university press, 2009.

      [53] Granovetter, M. S. (1973). "The Strength of Weak Ties" (PDF). The American Journal of Sociology. 78 (6): 1360–1380. doi:10.1086/225469. JSTOR 2776392.

      [54] Aarstad, J. (2014). Structural holes and entrepreneurial decision making. Entrepreneurship Research Journal, 4(3), 261–276.

      [55] Adams, M., Makramalla, M., & Miron, W. (2014). Down the rabbit hole: How structural holes in entrepreneurs’ social networks impact early venture growth. Technology Innovation Management Review, 4(9), 19–27.

      [56] Hunter III, D. & Chinta, R. (2013). Structural holes and banner ad click-throughs. Technology & Investment, 4, 30.44.

      [57] M. Rezvani, W. Liang, W. Xu, and C. Liu, “Identifying top-k structural hole spanners in large-scale social networks,†in Proc. 24th ACM Int. Conf. Inform. Knowl. Manage., 2015, pp. 263–272.

      [58] S. Chechik, E. Cohen, and H. Kaplan, “Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees,†in Proc. 18th Int. Workshop Approximation Algorithms Combinatorial Optimization Problems, 19th Int. Workshop Randomization Comput., 2015, pp. 659–679.

      [59] S. Goyal and F. Vega-Redondo, “Structural holes in social networks,†J. Econ. Theory, vol. 137, no. 1, pp. 460–492, Nov. 2007.

      [60] J. Tang, T. Lou, and J. Kleinberg, “Inferring social ties across heterogeneous networks,†in Proc. 5th ACM Int. Conf. Web Search Data Mining (WSDM), 2012, pp. 743–752.

      [61] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: bringing order to the web.†1999.

      [62] L. He, C. T. Lu, J. Ma, J. Cao, L. Shen, and P. S. Yu, “Joint community and structural hole spanner detection via harmonic modularity,†in Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2016, pp. 875–884.

      [63] T. Lou and J. Tang, “Mining structural hole spanners through information diffusion in social networks,†in Proc. ACM 22nd Int. Conf. World Wide Web (WWW), 2013, pp. 825–836.

  • Downloads

  • How to Cite

    Shruthi, K., & Y. Sri Lalitha, D. (2018). A Study of Identifying Structural Hole Spanners in Large Scale Networs. International Journal of Engineering & Technology, 7(3.24), 706-712. https://doi.org/10.14419/ijet.v7i3.24.24564

    Received date: 2018-12-22

    Accepted date: 2018-12-22