Structural cohesion

From InterSciWiki
Jump to: navigation, search

Contents

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

http://lists.gnu.org/archive/html/igraph-help/2012-03/msg00025.html

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
http://lists.gnu.org/archive/html/igraph-help/2012-03/msg00061.html
http://lists.gnu.org/archive/html/igraph-help/2012-03/msg00044.html

Cohesive blocking using iGraph in R - latest version

Introduction

PetersenGraph.jpg

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).

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

Egalitarian cohesion classroom - no bullying
Egalitarian cohesion classroom - bullying
Rightmost classroom types excluded

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

The example used by Moody and White 2003 in ASR colored by cohesion k





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")

Moody and White 2003

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

An example for community detection. These fail to recognize overlaps between communities as does cohesive blocking
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)

Click each image twice to enlarge.

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:

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

See also

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

References

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)

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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/
  6. 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
  7. 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.

  1. 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
  2. 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
  3. 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
  4. 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/
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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/
  1. footnote to 2001,2003

Talk

Talk:Structural Cohesion

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

Relational cohesion theory

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.”

Personal tools