Degree distributions of evolving alphabetic bipartite networks and their projections

Ganguly N, Ghosh S, Krüger T, Srivastava A (2012)
Theoretical Computer Science 466: 20-36.

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ;
Abstract
Many real-world systems are modeled as evolving bipartite networks and their one-mode projections. In particular, Discrete Combinatorial Systems (DCSs), which consist of a finite set of elementary units and different combinations of these units, can be modeled by a subclass of bipartite networks known as Alphabetic Bipartite Networks or alpha-BiNs, where the bottom partite-set contains a fixed number of nodes (the elementary units) and the top partite-set grows unboundedly with time through the addition of nodes (the combinations). The principal questions in the study of alpha-BIN evolution are to predict the degree distribution of the bottom set and that of the projection onto the bottom set (the bottom projection), from a knowledge of the bipartite growth dynamics. In this paper, we propose a realistic growth model for alpha-BiNs, where the degree distribution of the top set (i.e., the distribution of the number of elementary units in the composite entities in the DCS) can be any arbitrary distribution with finite first and second moments. Utilizing an exact correspondence between the preferential growth of alpha-BiNs and the Polya Urn scheme, we analytically solve the model to compute exact degree distributions of the bottom (fixed) set and the bottom projection. To the best of our knowledge, this is the first work which proposes and solves such a generalized growth model for alpha-BiNs. We also derive that the degree distributions of both the bottom set and the bottom projection, suitably normalized with time, converge to distributions that are invariant over time. We also verify that this improved model can accurately explain the degree distributions of several real-world DCSs and their projections. (C) 2012 Elsevier B.V. All rights reserved.
Publishing Year
ISSN
PUB-ID

Cite this

Ganguly N, Ghosh S, Krüger T, Srivastava A. Degree distributions of evolving alphabetic bipartite networks and their projections. Theoretical Computer Science. 2012;466:20-36.
Ganguly, N., Ghosh, S., Krüger, T., & Srivastava, A. (2012). Degree distributions of evolving alphabetic bipartite networks and their projections. Theoretical Computer Science, 466, 20-36.
Ganguly, N., Ghosh, S., Krüger, T., and Srivastava, A. (2012). Degree distributions of evolving alphabetic bipartite networks and their projections. Theoretical Computer Science 466, 20-36.
Ganguly, N., et al., 2012. Degree distributions of evolving alphabetic bipartite networks and their projections. Theoretical Computer Science, 466, p 20-36.
N. Ganguly, et al., “Degree distributions of evolving alphabetic bipartite networks and their projections”, Theoretical Computer Science, vol. 466, 2012, pp. 20-36.
Ganguly, N., Ghosh, S., Krüger, T., Srivastava, A.: Degree distributions of evolving alphabetic bipartite networks and their projections. Theoretical Computer Science. 466, 20-36 (2012).
Ganguly, Niloy, Ghosh, Saptarshi, Krüger, Tyll, and Srivastava, Ajitesh. “Degree distributions of evolving alphabetic bipartite networks and their projections”. Theoretical Computer Science 466 (2012): 20-36.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar