Power-law relations in random networks with communities

Random intersection graphs with communities

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.

Clustering spectrum of scale-free networks

Real-world networks often have power-law degrees and scale-free properties, such as ultrasmall distances and ultrafast information spreading. In this paper, we study a third universal property: three-point correlations that suppress the creation of triangles and signal the presence of hierarchy. We quantify this property in terms of c[over ¯](k), the probability that two neighbors of a degree-k node are neighbors themselves. We investigate how the clustering spectrum k↦c[over ¯](k) scales with k in the hidden-variable model and show that c[over ¯](k) follows a universal curve that consists of three k ranges where c[over ¯](k) remains flat, starts declining, and eventually settles on a power-law c[over ¯](k)∼k^{-α} with α depending on the power law of the degree distribution. We test these results against ten contemporary real-world networks and explain analytically why the universal curve properties only reveal themselves in large networks.

Epidemic spreading on complex networks with community structures

Many real-world networks display a community structure. We study two random graph models that create a network with similar community structure as a given network. One model preserves the exact community structure of the original network, while the other model only preserves the set of communities and the vertex degrees. These models show that community structure is an important determinant of the behavior of percolation processes on networks, such as information diffusion or virus spreading: the community structure can both enforce as well as inhibit diffusion processes. Our models further show that it is the mesoscopic set of communities that matters. The exact internal structures of communities barely influence the behavior of percolation processes across networks. This insensitivity is likely due to the relative denseness of the communities.