Bipartite network; Configuration model; Degree distributions; Generating functions; Heavy-tailed distribution; Node degree; Social and economic systems; Topology formation; Statistical and Nonlinear Physics; Statistics and Probability; Condensed Matter Physics; Physics - Physics and Society; Physics - Statistical Mechanics; cs.SI
Abstract :
[en] Bipartite (two-mode) networks are important in the analysis of social and economic systems as they explicitly show conceptual links between different types of entities. However, applications of such networks often work with a projected (one-mode) version of the original bipartite network. The topology of the projected network, and the dynamics that take place on it, are highly dependent on the degree distributions of the two different node types from the original bipartite structure. To date, the interaction between the degree distributions of bipartite networks and their one-mode projections is well understood for only a few cases, or for networks that satisfy a restrictive set of assumptions. Here we show a broader analysis in order to fill the gap left by previous studies. We use the formalism of generating functions to prove that the degree distributions of both node types in the original bipartite network affect the degree distribution in the projected version. To support our analysis, we simulate several types of synthetic bipartite networks using a configuration model where node degrees are assigned from specific probability distributions, ranging from peaked to heavy-tailed distributions. Our findings show that when projecting a bipartite network onto a particular set of nodes, the degree distribution for the resulting one-mode network follows the distribution of the nodes being projected on to, but only so long as the degree distribution for the opposite set of nodes does not have a heavier tail. Furthermore, we show that bipartite degree distributions are not the only feature driving topology formation of projected networks, in contrast to what is commonly described in the literature.
Disciplines :
Physics
Author, co-author :
VASQUES FILHO, Demival ; University of Luxembourg > Luxembourg Centre for Contemporary and Digital History (C2DH) > Digital History and Historiography
O'Neale, Dion R J; Department of Physics, University of Auckland, Private Bag 92019, Auckland, New Zealand and Te Pūnaha Matatini, University of Auckland, Private Bag 92019, Auckland, New Zealand
External co-authors :
yes
Language :
English
Title :
Degree distributions of bipartite networks and their projections.
The authors would like to thank Jurij Volčič and Mark Wilson for helpful conversations. This work was supported by funding from Callaghan Innovation, New Zealand.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
J. Koskinen and C. Edling, Soc. Networks 34, 309 (2012). 0378-8733 10.1016/j.socnet.2010.03.001
S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, Vol. 8 (Cambridge University Press, Cambridge, 1994).
R. Breiger, Soc. Forces 53, 181 (1974). 0037-7732 10.1093/sf/53.2.181
J. J. Ramasco, S. N. Dorogovtsev, and R. Pastor-Satorras, Phys. Rev. E 70, 036106 (2004). PLEEE8 1539-3755 10.1103/PhysRevE.70.036106
M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001). 1063-651X 10.1103/PhysRevE.64.026118
S. P. Borgatti and M. G. Everett, Soc. Netw. 19, 243 (1997). 0378-8733 10.1016/S0378-8733(96)00301-2
T. Zhou, J. Ren, M. Medo, and Y. C. Zhang, Phys. Rev. E 76, 046115 (2007). PLEEE8 1539-3755 10.1103/PhysRevE.76.046115
A. Mukherjee, M. Choudhury, and N. Ganguly, Physica A 390, 3602 (2011). PHYADX 0378-4371 10.1016/j.physa.2011.05.007
J. C. Nacher and T. Akutsu, Physica A 390, 4636 (2011). PHYADX 0378-4371 10.1016/j.physa.2011.06.073
J. Guillaume and M. Latapy, Physica A 371, 795 (2006). PHYADX 0378-4371 10.1016/j.physa.2006.04.047
F. Peruani, M. Choudhury, A. Mukherjee, and N. Ganguly, Europhys. Lett. 79, 28001 (2007). EULEEJ 0295-5075 10.1209/0295-5075/79/28001
M. Choudhury, N. Ganguly, A. Maiti, A. Mukherjee, L. Brusch, A. Deutsch, and F. Peruani, Phys. Rev. E 81, 036103 (2010). PLEEE8 1539-3755 10.1103/PhysRevE.81.036103
M. E. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001). PNASA6 0027-8424 10.1073/pnas.98.2.404
J. W. Grossman and P. D. F. Ion, Congressus Numerantium, 129 (1995).
D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998). NATUAS 0028-0836 10.1038/30918
L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, Proc. Natl. Acad. Sci. USA 97, 11149 (2000). PNASA6 0027-8424 10.1073/pnas.200327197
M. E. J. Newman, SIAM Rev. 45, 167 (2003). SIREAD 0036-1445 10.1137/S003614450342480
M. E. J. Newman, S. Forrest, and J. Balthrop, Phys. Rev. E 66, 035101 (R) (2002). 10.1103/PhysRevE.66.035101
R. Albert, H. Jeong, and A.-L. Barabasi, Nature (London) 401, 130 (1999). NATUAS 0028-0836 10.1038/43601
H. Jeong, S. P. Mason, A.-L. Barabasi, and Z. N. Oltvai, Nature (London) 411, 41 (2001). NATUAS 0028-0836 10.1038/35075138
N. D. Martinez, Ecol. Monogr. 61, 367 (1991). ECMOAQ 0012-9615 10.2307/2937047
M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002). 10.1103/PhysRevLett.89.208701
M. E. J. Newman, Phys. Rev. E 67, 026126 (2003). 1063-651X 10.1103/PhysRevE.67.026126
M. E. J. Newman and J. Park, Phys. Rev. E 68, 036122 (2003). 1063-651X 10.1103/PhysRevE.68.036122
H. S. Wilf, Generatingfunctionology (AK Peters, Natick, MA, 2005).
S. Pemmaraju and S. Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica® (Cambridge University Press, Cambridge, 2003).
W. Souma, Y. Fujiwara, and H. Aoyama, Physica A 324, 396 (2003). PHYADX 0378-4371 10.1016/S0378-4371(02)01858-7
M. E. J. Newman, Phys. Rev. E 64, 016131 (2001). 1063-651X 10.1103/PhysRevE.64.016131
R. N. Onody and P. A. de Castro, Phys. Rev. E 70, 037103 (2004). PLEEE8 1539-3755 10.1103/PhysRevE.70.037103
A. Gibbons, Algorithmic Graph Theory (Cambridge University Press, Cambridge, 1985).
D. B. West, Introduction to Graph Theory, Vol. 2 (Prentice Hall, Upper Saddle River, NJ, 2001).
J. L. Gross and J. Yellen, Graph Theory and Its Applications (CRC Press, New York, 2005).
B. Bollobás, Modern Graph Theory, Vol. 184 (Springer Science & Business Media, New York, 2013).
M. S. Granovetter, Am. J. Sociol. 78, 1360 (1973). 0002-9602 10.1086/225469
J. Clark and D. A. Holton, A First Look at Graph Theory (World Scientific, 1991).
M. E. J. Newman, Phys. Rev. E 64, 016132 (2001). 1063-651X 10.1103/PhysRevE.64.016132
J. J. Luczkovich, S. P. Borgatti, J. C. Johnson, and M. G. Everett, J. Theor. Biol. 220, 303 (2003). JTBIAP 0022-5193 10.1006/jtbi.2003.3147
R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach (Cambridge University Press, Cambridge, 2007).
A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani, Proc. Natl. Acad. Sci. USA 101, 3747 (2004). PNASA6 0027-8424 10.1073/pnas.0400087101
M. Li and B. Wang, in J. Phys. Conf. Ser., Vol. 604 (IOP Publishing, Bristol, 2015), p. 012013.
S. J. Miller, The Probability Lifesaver (Princeton University Press, Princeton, NJ, 2015).
E. A. Bender and E. R. Canfield, J. Comb. Theory, Ser. A 24, 296 (1978). JCBTA7 0097-3165 10.1016/0097-3165(78)90059-6
B. Bollobás, Eur. J. Combin. 1, 311 (1980). EJOCDI 0195-6698 10.1016/S0195-6698(80)80030-8
C. A. Hidalgo and R. Hausmann, Proc. Natl. Acad. Sci. USA 106, 10570 (2009). PNASA6 0027-8424 10.1073/pnas.0900943106
S. Battiston and M. Catanzaro, Eur. Phys. J. B 38, 345 (2004). EPJBFY 1434-6028 10.1140/epjb/e2004-00127-8
A. Abbasi, L. Hossain, S. Uddin, and K. J. Rasmussen, Scientometrics 89, 687 (2011). SCNTDX 0138-9130 10.1007/s11192-011-0463-1
A. Chakraborty and S. S. Manna, Phys. Rev. E 81, 016111 (2010). PLEEE8 1539-3755 10.1103/PhysRevE.81.016111
M. E. J. Newman, Phys. Rev. E 74, 036104 (2006). PLEEE8 1539-3755 10.1103/PhysRevE.74.036104
M. J. Barber, Phys. Rev. E 76, 066102 (2007). PLEEE8 1539-3755 10.1103/PhysRevE.76.066102
P. Zhang, J. Wang, X. Li, M. Li, Z. Di, and Y. Fan, Physica A 387, 6869 (2008). PHYADX 0378-4371 10.1016/j.physa.2008.09.006
D. B. Larremore, A. Clauset, and A. Z. Jacobs, Phys. Rev. E 90, 012805 (2014). PLEEE8 1539-3755 10.1103/PhysRevE.90.012805
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
