An official website of the United States government
Abstract Reciprocity in social networks is a measure of information exchange between two individuals, and indicates interaction patterns between pairs of users. A recent study finds that the reciprocity coefficient of a classical directed preferential attachment (PA) model does not match empirical evidence. Towards remedying this deficiency, we extend the classical three-scenario directed PA model by adding a parameter that controls the probability of creating a reciprocal edge. This proposed model also allows edge creation between two existing nodes, making it a realistic candidate for fitting to datasets. We provide and compare two estimation procedures for fitting the new reciprocity model and demonstrate the methods on simulated and real datasets. One estimation method requires careful analysis of the heavy tail properties of the model. The fitted models provide a good match with the empirical tail distributions of both in- and out-degrees but other mismatched diagnostics suggest that further generalization of the model is warranted.
more »
« less
Classes of preferential attachment and triangle preferential attachment models with power-law spectra
Abstract Preferential attachment (PA) models are a common class of graph models which have been used to explain why power-law distributions appear in the degree sequences of real network data. Among other properties of real-world networks, they commonly have non-trivial clustering coefficients due to an abundance of triangles as well as power laws in the eigenvalue spectra. Although there are triangle PA models and eigenvalue power laws in specific PA constructions, there are no results that existing constructions have both. In this article, we present a specific Triangle Generalized Preferential Attachment Model that, by construction, has non-trivial clustering. We further prove that this model has a power law in both the degree distribution and eigenvalue spectra.
more »
« less
- Award ID(s):
- 1909528
- PAR ID:
- 10285909
- Editor(s):
- Estrada, Ernesto
- Date Published:
- Journal Name:
- Journal of Complex Networks
- Volume:
- 8
- Issue:
- 4
- ISSN:
- 2051-1329
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Preferential attachment (PA) network models have a wide range of applications in various scientific disciplines. Efficient generation of large-scale PA networks helps uncover their structural properties and facilitate the development of associated analytical methodologies. Existing software packages only provide limited functions for this purpose with restricted configurations and efficiency. We present a generic, user-friendly implementation of weighted, directed PA network generation with R package wdnet. The core algorithm is based on an efficient binary tree approach. The package further allows adding multiple edges at a time, heterogeneous reciprocal edges, and user-specified preference functions. The engine under the hood is implemented in C++. Usages of the package are illustrated with detailed explanation. A benchmark study shows that wdnet is efficient for generating general PA networks not available in other packages. In restricted settings that can be handled by existing packages, wdnet provides comparable efficiency.more » « less
-
In recent years there has been significant interest in evolutionary analysis of large-scale networks. Researchers study network evolution rate and mechanisms, the impact of specific events on evolution, and spatial and spatio-temporal patterns. To support data scientists who are studying network evolution, there is a need to develop scalable and generalizable systems. Tangible systems progress in turn depends on the availability of standardized datasets on which performance can be tested. In this work, we make progress towards a data generator for evolving property graphs, which represent evolution of graph topology, and of vertex and edge attributes. We propose an attribute-based model of preferential attachment, and instantiate this model on a co-authorship network derived from DBLP, with attributes representing publication venues of the authors. We show that this attribute-based model predicts which edges are created more accurately than a structure-only model. Finally, we demonstrate that synthetic graphs are indeed useful for evaluating performance of evolving graph query primitives.more » « less
-
This article introduces a novel mutual informationbased measure to assess the glass ceiling effect in preferential attachment networks, which advances the analysis of inequalities in attributed networks. Using Shannon entropy and generalizing to Rényi entropy, our measure evaluates the conditional probability distributions of node attributes given the node degrees of adjacent nodes, which offers a more nuanced understanding of inequality compared to traditional methods that emphasize node degree distributions and degree assortativity alone. To evaluate the efficacy of the proposed measure, we evaluate it using an analytical structural inequality model as well as historical publication data. Results show that our mutual information measure aligns well with both the theoretical model and empirical data, underscoring its reliability as a robust approach for capturing inequalities in attributed networks. Moreover, we introduce a novel stochastic optimization algorithm that utilizes a parameterized conditional logit model for edge addition. Our algorithm is shown to outperform the baseline uniform distribution based approach in mitigating the glass ceiling effect. By strategically recommending links based on this algorithm, we can effectively hinder the glass ceiling effect within networks.more » « less
-
Abstract Preferential attachment, homophily, and their consequences such as scale-free (i.e. power-law) degree distributions, the glass ceiling effect (the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements) and perception bias are well-studied in undirected networks. However, such consequences and the factors that lead to their emergence in directed networks (e.g. author–citation graphs, Twitter) are yet to be coherently explained in an intuitive, theoretically tractable manner using a single dynamical model. To this end, we present a theoretical and numerical analysis of the novel Directed Mixed Preferential Attachment model in order to explain the emergence of scale-free degree distributions and the glass ceiling effect in directed networks with two groups (minority and majority). Specifically, we first derive closed-form expressions for the power-law exponents of the in-degree and out-degree distributions of each of the two groups and then compare the derived exponents with each other to obtain useful insights. These insights include answers to questions such as: when does the minority group have an out-degree (or in-degree) distribution with a heavier tail compared to the majority group? what factors cause the tail of the out-degree distribution of a group to be heavier than the tail of its own in-degree distribution? what effect does frequent addition of edges between existing nodes have on the in-degree and out-degree distributions of the majority and minority groups? Answers to these questions shed light on the interplay between structure (i.e. the in-degree and out-degree distributions of the two groups) and dynamics (characterized collectively by the homophily, preferential attachment, group sizes and growth dynamics) of various real-world directed networks. We also provide a novel definition of the glass ceiling faced by a group via the number of individuals with large out-degree (i.e. those with many followers) normalized by the number of individuals with large in-degree (i.e. those who follow many others) and then use it to characterize the conditions that cause the glass ceiling effect to emerge in a directed network. Our analytical results are supported by detailed numerical experiments. The DMPA model and its theoretical and numerical analysis provided in this article are useful for analysing various phenomena on directed networks in fields such as network science and computational social science.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/comnet/cnz040
