Mark E. J. Newman
Generalized Communities in Networks Newman, M. E. J.; Peixoto, Tiago P. PHYSICAL REVIEW LETTERS, 115 (8):10.1103/PhysRevLett.115.088701 AUG 20 2015 Key word SFI Taxonomy: Network Theory and Processes
- Abstract: A substantial volume of research is devoted to studies of community structure in networks, but communities are not the only possible form of large-scale network structure. Here, we describe a broad extension of community structure that encompasses traditional communities but includes a wide range of generalized structural patterns as well. We describe a principled method for detecting this generalized structure in empirical network data and demonstrate with real-world examples how it can be used to learn new things about the shape and meaning of networks.
Networks: An Introduction. Wonderful 2014 SFI business conference talk : Large-scale structure in networks. This video by Mark Newman, Large-scale structure in networks, gives about 14 new parameterized models for fitting network structure in large graphs, having thousands of millions of nodes. Well worth spending an hour and stopping to take notes on the math. They're all based on fitting model parameters, as in the maximization of the log-likelihood function: e.g., for estimating the parameters of the normal curve, for a series of points. Here, it is not just points but points and edges that are maximized by a log-likelihood function, which he gives for a series of types of graphs. See http://en.wikipedia.org/wiki/Normal_distribution#Estimation_of_parameters for the normal curve case, and the other functions are given on this blackboard.
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!!
Mark Newman's network data files (and see his Other sources of network data)
Newman, M. E. J. 2004 Coauthorship networks and patterns of scientific collaboration PNAS April 6, 2004 vol. 101 no. Suppl 1 5200-5205. Cited by Ernesto Estrada
Dolphin social network: an undirected social network of frequent associations between 62 dolphins in a community living off Doubtful Sound, New Zealand. Please cite D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, Evidence for social role in a dolphin social network Behavioral Ecology and Sociobiology 54, 396-405 (2003). email@example.com David Lusseau - Dolphin data.
Lusseau D, Newman MEJ (2004) Identifying the role that animals play in their social networks. Proc R Soc Lond B 271:S477–S481. Community detection
White, Douglas R.,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. Node-disjoint paths -- Discussion of pairwise cohesion
- Dear Doug,
Good to hear from you. Sorry for the slow reply -- it's a hectic time of the semester here.
I don't know if you recall, but we ended up not publishing the node-independent path calculation because someone (I forget who now) showed that the algorithm we were using is, in fact, exactly as fast (or as slow) as the augmenting path algorithm which returns the full (not approximate) number of node-independent paths. So it's always better to use the full algorithm. As far as I know, if you want all-pairs connectivity, either exact or approximate, there's no quicker way to get it than calculating the full Gomory-Hu tree (which I suppose is what you did in your calculations before). It's a polynomial-time calculation, O(n^3) I think, so doable for graphs up to about 10,000 nodes on an ordinary computer.
You could still do as you suggest and find k-cores first, then look for node-independent paths within that -- you'd just have to wrap the augmenting path calculation inside the k-cores calculation, but that would be straightforward programming I think.
Best wishes, Mark