# Structural cohesion

## 3-connected networks **new**

http://www.automata.rwth-aachen.de/~grohe/cap/kap-3cc.pdf

## Sinkovits

Robert_Sinkovits-_SDSC_Supercomputing#Finding_k-cohesive_groups_in_large_graphs

## Dwight Read

Dwight Read: I was looking at the preface of a book available online and read: "This book aims to address these questions and provide some ideas on how we may understand the principles that guide the development, stability and growth of complex social systems. The question which will be returned to is: what forces create and sustain an integrated whole? In other words, what exactly is ‘cohesion’, and why should we be concerned with its scientific investigation." The word cohesion caught my eye and I recall that this is something you have been concerned with. The book is "The Making of Society" 2011 by Robert G. Hercock. He goes on to say: "We are looking for deeper clues as to what makes society work, i.e. what processes foster cooperation, altruism and harmony in society. Some of the specific themes that will be addressed revolve around the impact of trust, consultation and cooperation, in the building of cohesive communities and organizations."

see also: ModuLand: Network Modules

- Vertex.connectivity in Igraph by Gabor Csardi corrected by to Massimo Franceschet March 2012. Anatomy of Cohesion - the k-graph. http://igraph.sourceforge.net/doc/R/cohesive.blocks.html -- http://igraph.wikidot.com/ -- http://igraph.sourceforge.net/doc/R/cohesive.blocks.html -- On Pairwise Connectivity of Wireless Multihop Networks - Felix Halim, Roland H.C. Yap, Yongzheng Wu. 2011. MapReduce-Based Maximum-Flow Algorithm for Large Small-World Network Graph ICDCS11 paper.

Dear Bob, as you will recall, one of the things we want to do this week is to compute matrices of pairwise cohesion for large undirected uniform edge-weighted networks. Then for any pair of nodes i,j, the pairwise cohesion is the minimum number of nodes on i-j paths whose removal disconnects them (Menger Theorem). It turns out that if each of two adjacent nodes on an i-j path is replaced by two nodes with a four-cycle among them and the new pairs of nodes adjacent to i and j have an incoming and outgoing arc respectively, then pairwise cohesion is calculated by a Ford-Fulkerman maxflow algorithm.

In 2011 Felix Halim, Roland H.C. Yap, and Yongzheng Wu devised a parallelized MapReduce-Based Maximum-Flow Algorithm for Large Small-World Network Graph in their ICDCS11 paper. The paper shows for a relatively small-world graph (moderate average distance) the the order of this computation is O(|f*|/A) where A is the augmenting paths per round and f* is the maxflow value which in our case is the number of node-independent paths. Parallelized, this is on the order O(|f*|), i.e., extremely efficient.

What we need is someone to examine this paper and help us parallelize this computation for one of the languages we can use in the workshop.

- http://igraph.sourceforge.net/doc/R/igraph.pdf search: Vertex.connectivity
- R: fixed vertex.connectivity documentation (thanks to Massimo Franceschet) Revision 2651. 15 Mar 2012

- Oh, actually there's a standard mapping from the node-cut problem to the edge-cut problem. It's described in my book (in chapter 11) among many other places (chapter 8: pp118). - Mark Newman. 2010. Networks: An Introduction by M. E. J. Newman. DRW: And it works!! buy book!
- Google scholar 209 citations to Moody and White 2003 - Friedkin review 2004

Cohesive blocking using iGraph in R - latest version

- Author(s) Doug White, Haiko Lietz -Z-0002Protected backup
- Structural cohesion references - Nested hierarchy
- Jure Leskovec, Daniel Huttenlocher, Jon Kleinberg et al 2010 Signed Networks in Social Media

## Introduction

**Structural cohesion** is the sociological and graph theory conception ^{[1]} and measurement of cohesion for maximal social group or network boundaries where related elements cannot be disconnected except by removal of a certain minimal number of other nodes. The solution to the boundary problem for structural cohesion is found by the vertex-cut version of Menger's theorem. It is also useful to know that k-cohesive graphs (or k-components) are always a subgraph of a k-core, although a k-core is not always k-cohesive. A k-core is simply a subgraph in which all nodes have at least k neighbors but it need not even be connected. (See the related but contrastive concept and measure for Intercohesion).

- Ron Aharoni and Eli Berger. 2005. Menger's theorem for Infinite graphs.

A vertex cut for a graph or subgraph is equivalent to the minimum number of vertex-disjoint paths connecting every pair of vertices in the (sub-)graph. Finding this maximum is an optimization problem that is NP-complete but admits solutions in which the computation time depends on the network topology. The following bibliography is from M. Blesa and C. Blum: vertex-disjoint paths

## Examples

Some illustrative examples are presented in the gallery below:

Jai-Jeong Ahn - Nested hierarchy

## Significance

Structural cohesion provides an especially important measure of the organizational components of networks because it is isomorphic to the measure of structural traversal. Together, this isomorphism provides an essential scientific definition and measure of what is commonly meant by *cohesion*, in its two basic aspects, when looking at actual behavior: resistance to dissolution under external perturbation (the *external* part of cohesion) and internal connectivity and capability for coordinated or amplified reaction within the elements that cohere (the *internal* part of cohesion). This is a perfectly general *concept* across the sciences and humanities, but having a common network *measure* of structural cohesion is enormously important for the formulation and testing of general theories. Predictive structural cohesion theory is aimed at making, testing, and refining predictions about the consequences of the distributions of structurally cohesive units on dynamical outcomes of network interaction.

Dwight Read: I was looking at the preface of a book available online and read: "This book aims to address these questions and provide some ideas on how we may understand the principles that guide the development, stability and growth of complex social systems. The question which will be returned to is: what forces create and sustain an integrated whole? In other words, what exactly is ‘cohesion’, and why should we be concerned with its scientific investigation. " The word cohesion caught my eye and I recall that this is something you have been concerned with. The book can be read online at http://agentdynamics.files.wordpress.com/2011/07/cohesion-book1.pdf and is called "The Making of Society" by Robert G. Hercock.

## Install R, Cut and Paste to do Calculation

A program for calculating all maximal network subgroups with (structurally cohesive) connectivity-k was defined in Moody and White (2003) and programmed by James Moody in SAS. See **Peter McMahan** for his implementation of the algorithm programmed in R, at http://intersci.ss.uci.edu/wiki/pub/CohesiveBlocks.R

Install or start R: go to R/Package & Data/Package installer, search for "igraph", install, then Cut and paste into R as a command source("http://intersci.ss.uci.edu/wiki/pub/MW.R")

## Pairwise k-cohesion

Douglas R. White and Mark E.J. Newman. 2001. Fast Approximation Algorithms for Finding (Multiple) Node-Independent Paths in Networks Santa Fe Institute Working Paper 01-07-035.

### This works for large graphs

Use UCInet to run Pairwise cohesion. Then multiply the 0/1 image of the graph by the Pairwise cohesion matrix. Then read in Pajek and use spring embedding. Run for each value 2 to max value on edges find the bicomponents with /Net/Components/Bicomponents. You can also try /Hierarchy.

## Community structure and structural cohesion

**20 sociologists can be wrong**- Meta-analysis: Finding Social Groups: A Meta-Analysis of the Southern Women Data[1] In, Ronald Breiger, Kathleen Carley and Philippa Pattison (eds.) Dynamic Social Network Modeling and Analysis. Washington, D.C.:The National Academies Press, 2003.Reprinted: Social Networks Analysis. Four Volume Set. Edited by: Linton Freeman
- cohesive.blocks(of the Southern Women)

- Meta-analysis: Finding Social Groups: A Meta-Analysis of the Southern Women Data[1] In, Ronald Breiger, Kathleen Carley and Philippa Pattison (eds.) Dynamic Social Network Modeling and Analysis. Washington, D.C.:The National Academies Press, 2003.Reprinted: Social Networks Analysis. Four Volume Set. Edited by: Linton Freeman

**Click each image twice to enlarge.**

In the third image, 20 of 21 studies are incorrect as to cohesive blocks and community structure. |

Install R, then cut and paste into R as a command source("http://intersci.ss.uci.edu/wiki/Vlado/DavisNet32.R") #works - right bipartite dataset matches DGG table

As Freeman notes, **DGG** (quote): collected systematic data on the social activities of 18 women whom they observed over a nine-month period. During that period, various subsets of these women had met in a series of 14 informal social events. The participation of women in events was uncovered using “interviews, the records of participant observers, guest lists, and the newspapers” (**DGG**, p. 149). Homans (1950, p. 82), who presumably had been in touch with the research team, reported that the data reflect joint activities like, “a day’s work behind the counter of a store, a meeting of a women’s club, a church supper, a card party, a supper party, a meeting of the Parent-Teacher Association, etc.”

The table in which the data on attendance are noted distinguishes between "Miss" and "Mrs" for each woman and we assume that those at the Parent-Teacher Association meetings (with children) are married while in the 1930s "work behind the counter of a store" are more likely "Miss." While that separation is almost perfectly reflected in the attendance data contrasts among two more restricted sets of events, four of the events connect both subsets, lending the overall cohesion to the two-mode network.

Restart R: then Cut and paste into R as a command source("http://intersci.ss.uci.edu/wiki/pub/MW.R") source("http://intersci.ss.uci.edu/wiki/Vlado/MW.R")

## Evidence for Structurally cohesive Sexually transmitted disease networks STD cores

[www.ima.umn.edu/talks/workshops/11-17-21.2003/moody/moody.ppt Epidemic Potential in Human Sexual Networks:. Connectivity and The Development of STD Cores] 2003 James Moody

## Something new

Before the Moody and White (2003) paper was published, Doug White and Mark Newman (2001), just as White and Harary (2001) was published, got together and did an SFI working paper on Fast Approximation Algorithms for Finding Node-Independent Paths in Networks which was soon implemented in UCInet. Problem was, as Jean Pierre Eckmann convinced me in his work on curvature these did not form a tight topological structure like Watt's clustering or (now) Vicsek's clique percolation, and having a matrix of number of node independent paths (NIPs) didn't make it easier to find connectivity-k structural cohesion. But like Newman's community finding by a Hierarchical Clustering Analysis of betweeness centrality (HCA), and HCA of NIPs would make a very nice analysis of comm8unity cohesion. Would make a simple experiment in UCInet.WikiSysopWikiSysop 20:45, 13 February 2008 (PST)

see "curvature" for a pdf of Eckmann's reciprocity analysis of community structure. also Dialog in e-Mail Traffic Jean-Pierre Eckmann, Elisha Moses, Danilo Sergi

THE METHOD as a procedure in UCInet:

- Network/Cohesion/Point Connectivity - produces a "PointConnectivity" output file
- Tools/Cluster/Hierarchical/Similarities read in "PointConnectivity" (or however it was renamed)
- There will be cohesive blocks!

## See also

- Peter McMahan R software for calculating structural cohesion by the Moody-White 2003 algorithm
- Cohesive blocking a more condensed form of the above
- J. Ruan and W. Zhang, 2008. Identifying network communities with a high resolution, Physical Review E, 77:016104
- Southern women example
- Social network
- Social-circles network model
- Clique percolation
- Graph cuts in vision and image processing
- Clique size, group size, and brain size
- Perceived cohesion

http://www.coi.columbia.edu/pdf/stark_vedres_pbt.pdf

## References

- Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM Journal on Computing 14: 862–874.
- M.G. Everett, S.P. Borgatti. 2000. Peripheries of cohesive subsets. Social Networks 01/2000 21(4).
- DRW TOPICS

**NETWORKS**: structural cohesion, tie-generation dynamics, organizational and field dynamics, complex networks social circles model, parameterized simulation of feedback networks

(drw=Douglas R. White, see http://intersci.ss.uci.edu/wiki/index.php/Publications_of_Douglas_R._White)

- 2001 The Cohesiveness of Blocks in Social Networks: Node Connectivity and Conditional Density. (drw & Frank Harary), Sociological Methodology 2001 (31):305-359. http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF http://www.ingentaconnect.com/content/bpl/some/2001/00000031/00000001;jsessionid=caew7r81aa3c.henrietta
- 2003 Structural Cohesion and Embeddedness: A Hierarchical Conception of Social Groups. (J. Moody, drw) American Sociological Review 68(1):1-25. 2004 Outstanding Article Award in Mathematical Sociology. American Sociological Association. http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf
- 2005 Network Dynamics and Field Evolution: The Growth of Interorganizational Collaboration in the Life Sciences. (W. W. Powell, drw, K. W. Koput & J. Owen-Smith) American Journal of Sociology 110(4):901-975. AJS enhanced text and PDF. Viviana Zelizer Best Paper in Economic Sociology Award (2005-2006), American Sociological Association. http://www.journals.uchicago.edu/doi/abs/10.1086/421508
- 2004 Networks, Fields and Organizations: Micro-dynamics, scale and cohesive embeddings (drw, W. W. Powell, J. Owen-Smith. J. Moody) Computational and Mathematical Organization Theory 10(1):95-117. http://repositories.cdlib.org/postprints/10/ http://tinyurl.com/39f5a8
- 2004 Network Analysis, Social Dynamics and Feedback in Social Systems. Cybernetics and Systems 35(2-3):173-192. http://eclectic.ss.uci.edu/~drwhite/pub/White_EMCSR2a.pdf http://tinyurl.com/3beqq2/
- 2006 A Generative Model for Feedback Networks. drw, Nataša Kejžar, Constantino Tsallis, Doyne Farmer, and Scott White. Physical Review E, 016119 11pp. http://arxiv.org/abs/cond-mat/0508028 http://tinyurl.com/ylpbn3 http://en.wikipedia.org/wiki/Social-circles_network_model
- 2008 Opening Closure: Intercohesion and Entrepreneurial Dynamics in Business Groups. Balazs Vedres and David Stark. http://www.chicagogsb.edu/socialorg/docs/Stark-OpenClosure.pdf
**KINSHIP NETWORKS**: cohesive structural endogamy, social class, complexity, evolutionary resilience

The boundaries of structural endogamy are a special case of structural cohesion.

- 1992 Representing and Computing Kinship: A New Approach. (drw & P. Jorion). Current Anthropology 33(4): 454-463. http://eclectic.ss.uci.edu/~drwhite/pw/White-Jorion1992.pdf
- 1996 Les structures réticulaires de la pratique matrimoniale. (M. Houseman & drw) L'Homme 139: 59-85. http://tinyurl.com/2k5czp http://eclectic.ss.uci.edu/~drwhite/pub/StructureReticulaire.pdf
- 1997 Structural Endogamy and the Graphe de Parenté. Mathématiques, Informatique, et Sciences Humaines 137:107-125. http:/eclectic.ss.uci.edu/~drwhite/pw/str-endo.pdf
- 1997 Class, Property and Structural Endogamy: Visualizing Networked Histories. (L. A. Brudner & drw). Theory and Society 25(2):161-208. http://repositories.cdlib.org/postprints/3/
- 1998 Network Mediation of Exchange Structures: Ambilateral Sidedness and Property Flows in Pul Eliya (M. Houseman & drw). pp. 59-89 in Kinship, Networks and Exchange, eds. T. Schweizer and drw. Cambridge University Press. http://eclectic.ss.uci.edu/~drwhite/pub/PUL-CAMB1a.pdf http://tinyurl.com/2lb2gu http://www.ivry.cnrs.fr/spafrican/chercheurs/articles/Network%20Mediation.pdf
- 1998 Kinship, Property Transmission, and Stratification in Javanese Villages. (drw & T. Schweizer). pp. 59-89 in Kinship, Networks and Exchange, eds. T. Schweizer and drw. Cambridge University Press. http://eclectic.ss.uci.edu/~drwhite/pub/JAV1.pdf
- 1999 Controlled Simulation of Marriage Systems. Journal of Artificial Societies and Social Simulation 2(3). http://jasss.soc.surrey.ac.uk/2/3/5.html
- 2002 Navigability of Strong Ties: Small Worlds, Tie Strength and Network Topology. (drw & M. Houseman). Complexity 8(1):72-81 http://eclectic.ss.uci.edu/~drwhite/Complexity/SpecialIssue.htm
- 2005 Chapter1 Network Analysis and Ethnographic Problems: Process Models of a Turkish Nomad Clan. drw & Ulla Johansen. Boston: Lexington Press. 2006 Paper http://eclectic.ss.uci.edu/~drwhite/pub/PMContFwd01.pdf
- 2004 Ring Cohesion Theory in Marriage and Social Networks. Mathématiques et sciences humaines 43(168):5-28 http://www.ehess.fr/revue-msh/recherche.php?numero=168 http://eclectic.ss.uci.edu/download/MarriageNetTools.htm
- 2004 Matrimonial Ring Structures (Klaus Hamberger, Michael Houseman, Isabelle Daillant, Douglas R. White and Laurent Barry). Mathématiques et sciences humaines 43(168):83-121. http://eclectic.ss.uci.edu/download/MarriageNetTools.htm
- 2005 Multiple Measures of Alyawarra Kinship. (Woodrow W. Denham and drw) Field Methods 17: 70-101. http://eclectic.ss.uci.edu/~drwhite/pw/MultiMeas03a.pdf http://fmx.sagepub.com/content/vol17/issue1/

- ↑ footnote to 2001,2003

## Talk

Structure k-cohesion experiment

## Instances and best known solutions for those instances for Edge disjoint paths: very different from Node disjoint paths however

The first set of benchmark instances available for the EDP problem was proposed in [BB04]. The same authors are currently working on a more sophisticated version of the algorithm that is achieving better results and that enlarges the set of benchmark instances with some graphs that exemplify Internet topologies.

### Related Papers:

[BB04] M. Blesa and C. Blum. Ant colony optimization for the maximum edge-disjoint paths problem. In Raidl et al., editor, 1st European Workshop on Evolutionary Computation in Communications, Networks, and Connected Systems (EvoCOMNET'04), in Applications of Evolutionary Computing (EvoWorkshops'04), volume 3005 of Lecture Notes in Computer Science, pages 160-169, Coimbra, Portugal, April 2004. Springer-Verlag Heidelberg.

[Kar72] R. Karp. Complexity of Computer Computations, chapter Reducibility among combinatorial problems, pages 85-103. R.E. Miller and J.W.Thatcher (Eds.). Plenum Press, New York, 1972.

[Kle96] Jon Kleinberg. Approximation algorithms for disjoint paths problems. PhD Thesis, MIT, Cambridge, USA, May 1996.

[MP93] M.Middendorf and F.Pfeiffer. On the complexity of the disjoint paths problem. Combinatorica, 13:97-107, 1993.

[Vyg95] J.Vygen. NP-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61:83-90, 1995.

## See also

Structural cohesion references

## Supercomputing

Modeling Human Societies

Doug White, a professor of anthropology at UC Irvine, is interested in how societies, cultures, social roles, and historical agents of change evolve dynamically out of multiple networks of social action. In the 1990s he and his colleagues discovered that networks could be meaningfully analyzed by a new algorithm that derives from one of the basic theorems in graph theory, the Menger vertex-connectivity theorem (1927). Computer scientists had coded Menger's edge-connectivity theorem, known as the Max-Flow (Ford-Fulkerson) network algorithm, used to optimize the routing of traffic. But Menger's theorem also proved that vertex-connectivity -- the internal cohesion of some minimum number of disjoint paths between every pair of members in a group -- is equivalent to the group’s external cohesion: resistance to threat of disconnection by removal of group members. Vertex-connectivity was thought by computer scientists to be intractable. White and Harary showed that groups defined in this way obeyed a law-like regularity where members of a group under threat of disruption from competing leaders tended to dissolve their ties in the particular order of members with lowest cohesion. Further research by White and grad student James Moody led to a formal algorithm that identified the boundaries of cohesive groups, with structural cohesion defined as the minimal number of actors who, if removed from a group, would disconnect the group. Using data from network studies in ten U.S. high schools, they found that level of cohesion for each student predicted their levels of attachment to school as measured on a three-item questionnaire. In repeated experiments with many different kinds of datasets, structural cohesion was found to predict political attachments, attachment to community, intra-group cooperation, partnership formation, social integration, and well-being.

Finding the boundaries of cohesive subgroups, however, remain a challenge for computation, far more challenging than finding cliques of fully connected sets of vertices within a graph. White and his team are currently testing their recently developed software on synthetic networks constructed from well-known models, and plan to apply their methods to data sets derived from networks of co-‐authorship, benefits of marriage alliances, and splits in the scientific citation networks in periods of contention. The most computationally difficult step in team's design of new high-perforamce software requires the construction of the pairwise cohesion matrix (PCM), which in turn requires the calculation of the number of vertex-independent paths between all pairs of vertices in the network,” said White.

The researchers ported the application to Gordon’s vSMP nodes following guidelines provided by ScaleMP. For larger graphs, such as a 2400 vertex network built using the Watts-Strogatz small-world model, near linear scalability was achieved when using all 256 cores (an estimated 243x speedup relative to one core). In the original version of the application, memory beyond that available on a single physical node was needed, but restructuring of the code transformed it from memory to compute limited.

“We’re coordinating teams at UC Irvine, UC San Diego, the Santa Fe Institute, and Argonne National Laboratory to do the Wiley-Blackwell Companion to Cross-Cultural Research as a cutting-edge guide to an emerging use of supercomputing: the development, after 130 years, of solutions to missing data imputation, Galton’s problem of nonindependence of cases, and inferential statistics that finally put comparative research on a solid footing of replicable scientific findings comparable from small to large and super-large datasets,” said White.

White added that the group is still working on easier modeling on a virtual machine to enter dependent and independent variables iterated with development of complex models that feed into bigger integrative models for sociocultural, political-economic, environmental, and historical processes. “Many of these problems couple the network analyses done on Gordon, with inferential statistics run on SDSC’s Trestles supercomputer to form a single Complex Social Science (CoSSci) Gateway.”