Pairwise cohesion algorithm
- Anatomy of Cohesion: The k-graph
- Vertex.connectivity in Igraph by Gabor Csardi corrected by to Massimo Franceschet March 2012.
- 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
- Mark Newman: there's actually 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! The diagrams below are from pp342-343 of Newman's book explicating Gabor Csardi's new method. After converting a graph like (a) to the form in (b), the Ford-Fulkerson algorithm is run to count the number of node-independent paths between every pair of nodes. Computational time is o(n3) at the upper limit but the Wikipedia:Ford–Fulkerson_algorithm#Complexity with integer values is very low.
- Wikipedia:Ford–Fulkerson_algorithm#Complexity: "When the capacities are integers, the runtime of Ford-Fulkerson is bounded by (see Wikipedia:big O notation), where is the number of edges in the graph and is the maximum flow in the graph. This is because each augmenting path can be found in time and increases the flow by an integer amount which is at least ."
- A great advantage of this computational complexity is that the Csardi flow computation method for pairwise cohesion is not only efficient but also calculates a pairwise integer flow-computation for every pair of nodes.