Preferential Attachment Graphs with Planted Communities
This work addresses the modeling of community structures in network growth for researchers in graph theory and network science, but it is incremental as it extends an existing model.
The authors introduced a variant of the preferential attachment model that incorporates planted communities, showing that the fraction of half-edges attached to vertices with a given label converges almost surely and the empirical degree distribution for each community converges to a heavy-tailed distribution with potentially different tail decay parameters.
A variation of the preferential attachment random graph model of Barabási and Albert is defined that incorporates planted communities. The graph is built progressively, with new vertices attaching to the existing ones one-by-one. At every step, the incoming vertex is randomly assigned a label, which represents a community it belongs to. This vertex then chooses certain vertices as its neighbors, with the choice of each vertex being proportional to the degree of the vertex multiplied by an affinity depending on the labels of the new vertex and a potential neighbor. It is shown that the fraction of half-edges attached to vertices with a given label converges almost surely for some classes of affinity matrices. In addition, the empirical degree distribution for the set of vertices with a given label converges to a heavy tailed distribution, such that the tail decay parameter can be different for different communities. Our proof method may be of independent interest, both for the classical Barabási -Albert model and for other possible extensions.