Structural Cohesion: Visualization and Heuristics for Fast Computation


Share / Export Citation / Email / Print / Text size:

Journal of Social Structure

International Network for Social Network Analysis

Subject: Social Sciences


eISSN: 1529-1227





Volume / Issue / page

Volume 21 (2020)
Volume 20 (2019)
Volume 19 (2018)
Volume 18 (2017)
Volume 17 (2016)
Volume 16 (2015)
Volume 15 (2014)
Volume 14 (2013)
Volume 13 (2012)
Volume 12 (2011)
Volume 11 (2010)
Volume 10 (2009)
Related articles

VOLUME 16 , ISSUE 1 (December 2015) > List of articles

Structural Cohesion: Visualization and Heuristics for Fast Computation

Jordi Torrents / Fabrizio Ferraro

Citation Information : Journal of Social Structure. Volume 16, Issue 1, Pages 1-36, DOI:

License : (CC BY-NC 4.0)

Published Online: 13-August-2019



The structural cohesion model is a powerful theoretical conception of cohesion in social groups, but its diffusion in empirical literature has been hampered by operationalization and computational problems. In this paper, we start from the classic definition of structural cohesion as the minimum number of actors who need to be removed in a network in order to disconnect it, and extend it by using average node connectivity as a finer grained measure of cohesion. We present useful heuristics for computing structural cohesion that allow a speed-up of one order of magnitude over the algorithms currently available. We analyze three large collaboration networks (co-maintenance of Debian packages, co-authorship in Nuclear Theory and High-Energy Theory) and show how our approach can help researchers measure structural cohesion in relatively large networks. We also introduce a novel graphical representation of the structural cohesion analysis to quickly spot differences across networks.

Content not available PDF Share



Abelson, H., G. Sussman, J. Sussman, and A. Perlis (1985). Structure and interpretation of computer programs, Volume 2. MIT Press Cambridge, MA.

Ahmed, A., V. Batagelj, X. Fu, S.-H. Hong, D. Merrick, and A. Mrvar (2007). Visualisation and analysis of the internet movie database. In Visualization, 2007. APVIS’07. 2007 6th International Asia-Pacific Symposium on, pp. 17–24. IEEE.

Albert, R., H. Jeong, and A. Barabási (2000). Error and attack tolerance of complex networks. Nature 406(6794), 378–382.

Batagelj, V. and M. Zaveršnik (2011). Fast algorithmsfor determining (generalized) core groups in social networks. Advances in Data Analysis and Classification 5(2), 129–145.

Beineke, L., O. Oellermann, and R. Pippert (2002). The average connectivity of a graph. Discrete mathematics 252(1-3), 31–45.

Bolz, C., A. Cuni, M. Fijalkowski, and A. Rigo (2009). Tracing the meta-level: Pypy’s tracing jit compiler. In Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, pp. 18–25. ACM.

Brandes, U. and T. Erlebach (2005). Network analysis: methodological foundations, Volume 3418. Springer Verlag.

Csárdi, G. and T. Nepusz (2006). The igraph software package for complex network research.

Dodds, P., D. Watts, and C. Sabel (2003). Information exchange and the robustness of organizational networks. Proceedings of the National Academy of Sciences 100(21), 12516.

Ellson, J., E. Gansner, L. Koutsofios, S. North, and G. Woodhull (2002). Graphviz—open source graph drawing tools. In Graph Drawing, pp. 594–597. Springer.

Fortunato, S. (2010). Community detection in graphs. Physics Reports 486(3-5), 75–174.

Grannis, R. (2009). Paths and semipaths: reconceptualizing structural cohesion in terms of directed relations. Sociological Methodology 39(1), 117–150.

Granovetter, M. (1985). Economic action and social structure: the problem of embeddedness. American Journal of Sociology 91(3), 481.

Gutwenger, C. and P. Mutzel (2001). A linear time implementation of spqr-trees. In Graph Drawing, pp. 77–90. Springer.

Hagberg, A., D. Schult, and P. Swart (2008, August). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy2008), Pasadena, CA USA, pp. 11–15.

Hopcroft, J. and R. Tarjan (1974). Dividing a graph into triconnected components.

Hunter, J. D. (2007). Matplotlib: A 2d graphics environment. Computing In Science & Engineering 9(3), 90–95.

Jones, E., T. Oliphant, P. Peterson, et al. (2001). SciPy: Open source scientific tools for Python.

Kamada, T. and S. Kawai (1989). An algorithm for drawing general undirected graphs. Information processing letters 31(1), 7–15.

Kanevsky, A. (1993). Finding all minimum-size separating vertex sets in a graph. Networks 23(6), 533–541.

Latapy, M., C. Magnien, and N. Vecchio (2008). Basic notions for the analysis of large twomode networks. Social Networks 30(1), 31–48.

Lind, P., M. Gonzalez, and H. Herrmann (2005). Cycles and clustering in bipartite networks. Physical Review E 72(5), 56127.

Mani, D. and J. Moody (2014). Moving beyond stylized economic network models: The hybrid world of the indian firm ownership network. American Journal of Sociology 119(6), pp. 1629–1669.

Moody, J. (2004). The structure of a social science collaboration network: Disciplinary cohesion from 1963 to 1999. American Sociological Review 69(2), 213–238.

Moody, J., D. McFarland, and S. Bender-deMoll (2005). Dynamic network visualization. American Journal of Sociology 110(4), 1206–1241.

Moody, J. and D. White (2003). Social cohesion and embeddedness: A hierarchical conception of social groups. American Sociological Review 68(1), 103–28.

Newman, M. (2003). The structure and function of complex networks. SIAM Review 45, 167.

O’Mahony, S. and F. Ferraro (2007). The emergence of governance in an open source community. The Academy of Management Journal 50(5), 1079–1106.

Opsahl, T. (2011). Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks 34.

Pérez, F. and B. E. Granger (2007, May). IPython: a System for Interactive Scientific Computing. Comput. Sci. Eng. 9(3), 21–29.

Powell, W., D. White, K. Koput, and J. Owen-Smith (2005). Network dynamics and field evolution: The growth of interorganizational collaboration in the life sciences. American journal of sociology 110(4), 1132–1205.

Robins, G. and M. Alexander (2004). Small worlds among interlocking directors: Network structure and distance in bipartite graphs. Computational & Mathematical Organization Theory 10(1), 69–94.

Seidman, S. (1983). Network structure and minimum degree. Social networks 5(3), 269–287.

Shwed, U. and P. Bearman (2010). The temporal structure of scientific consensus formation. American sociological review 75(6), 817–840.

Tarjan, R. (1972). Depth-first search and linear graph algorithms. In Switching and Automata Theory, 1971., 12th Annual Symposium on, pp. 114–121. IEEE.

Uzzi, B., L. Amaral, and F. Reed-Tsochas (2007). Small-world networks and management science research: a review. European Management Review 4(2), 77–91.

Van Rossum, G. (1995). Python reference manual. Centrum voor Wiskunde en Informatica.

Wasserman, S. and K. Faust (1994). Social network analysis: Methods and applications. Cambridge University Press.

White, D. and F. Harary (2001). The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology, 305–359.

White, D. and M. Newman (2001). Fast approximation algorithms for finding node-independent paths in networks. Santa Fe Institute Working Papers Series.

White, D., J. Owen-Smith, J. Moody, and W. Powell (2004). Networks, fields and organizations: micro-dynamics, scale and cohesive embeddings. Computational & Mathematical Organization Theory 10(1), 95–117.