SPA is a discrete growth process for networks featuring scale-free and overlapping community structure.
It models two phenomena simultaneously: the growth of community structure and the growth of the internal structure of communities.
In the growth of community structure, a vertex joins a community by creating an edge with an existing member.
The vertex (community) is a new one with probability p (q), and otherwise chosen within the existing set of vertices (communities) preferentially.
In so doing, SPA generates a network whose building blocks are overlapping groups of scale-free distributed communities.
The internal structure of communities is determined by an intuitive densification process.
A link is added between two vertices members of a same community, at a rate which is controlled by a third parameter, r.
Higher values leads to denser (more connected) communities.
The structural properties below only start to illustrate the richness of the SPA process.
The average number of edges, and thus of neighbours, per vertex.Further Reading
Average probability that two neighbours of a given vertex are themselves connected.Further Reading
Correlation coefficient between the degree of a given vertex and its neighbours' degrees.Further Reading
Maximum average degree within the most interconnected subset of the network.Further Reading
The maximum number of vertices that are found within a community.Further Reading
The maximum number of communities in which a vertex appears.Further Reading
The average fraction of possible edges that actually appear within communities.Further Reading
Similarity of the set of vertices of two randomly selected communities.Further Reading
The running time explodes for extremal values of p, q, and r.
Since the structural properties vary continuously with the parameters, similar parameters generate similar networks.
Hence, a small subset of qualitatively different networks can give us a good idea of what's going on.
We identified nine representative sets of parameters by
|p||q||r||Density||Clustering||Degree assortativity||Maximal coreness||Largest community||Highest membership||Partition density||Average overlap|
The SPA process generates realistic synthetic networks with a known overlapping community structure.
Many algorithms aim to uncover such communities in empirical datasets, and telling them apart calls for good benchmarking tools.
It's a straightforward process.
One simply needs to produce an SPA network, use a detection algorithm to recover its community structure, and compare the results with the known communities (using the Normalized Mutual Information, for instance).
Below, we applied state-of-the-art community detection algorithms to the nine representative subsets of networks.
And we found pretty interesting results.
Infomap infers the community structure from the flow of information.Further Reading
BigCLAM fits a generative model to empirical datasets using a coordinate descent.Further Reading
COPRA uses the steady state of a label propagation dynamics to determine the assignment of nodes to communities.Further Reading
OSLOM optimizes a fitness function that expresses the statistical significance of communities with respect to random fluctuations.Further Reading
Of course, this list is far from complete, so
and we'll add your algorithm here.
Or you can simply download the software below.