Z-0002bak

From InterSciWiki
Jump to: navigation, search

Cohesive blocking using iGraph in R - latest version

Contents

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:

  • A 6-node ring with connectivity-2 structural cohesion - removal of two nodes is needed to disconnect it.

  • The 6-node component (1-connected) has an embedded 2-component, nodes 1-5.

  • A 6-node clique is a 5-component, structural cohesion 5.

  • Davis's Southern Women data (click to enlarge) colored by cohesion k.

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.

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

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

Structural cohesion - - Protected backup0002

Retrieved from "http://intersci.ss.uci.edu/wiki/index.php?title=Z-0002bak&oldid=57104"
Personal tools