Internal links and pairs as a new tool for the analysis of bipartite complex networks

被引：3

作者：

Allali O. ^{[1
]}

Tabourier L. ^{[1
]}

Magnien C. ^{[1
]}

Latapy M. ^{[1
]}

机构：

[1] LIP6, University Pierre and Marie Curie, 4 Place Jussieu, Paris

来源：

Social Network Analysis and Mining | 2013年 / 3卷 / 1期

关键词：

Bipartite graphs; Graph storage; Internal links; One-mode projection; Real-world networks;

D O I：

10.1007/s13278-012-0053-0

中图分类号：

学科分类号：

摘要：

Many real-world complex networks are best modeled as bipartite (or 2-mode) graphs, where nodes are divided into two sets with links connecting one side to the other. However, there is currently a lack of methods to analyze properly such graphs as most existing measures and methods are suited to classical graphs. A usual but limited approach consists in deriving 1-mode graphs (called projections) from the underlying bipartite structure, though it causes important loss of information and data storage issues. We introduce here internal links and pairs as a new notion useful for a bipartite analysis, which gives insights into the information lost by projecting the bipartite graph. We illustrate the relevance of these concepts in several real-world instances, illustrating how it enables to discriminate behaviors among various cases when we compare them to a benchmark of random graphs. Then, we show that we can draw benefit from this concept for both modeling complex networks and storing them in a compact format. © 2012, Springer-Verlag.

引用

页码：85 / 91

页数：6

共 12 条

[1]

Aidouni F., Latapy M., Magnien C., Ten weeks in the life of an eDonkey server. In: Proceedings of the 2009 IEEE international symposium on parallel and distributed processing, pp 1–5, (2009)

[2]

Allali O., Magnien C., Latapy M., Link prediction in bipartite graphs using internal links and weighted projection. In: Proceedings of the 2011 IEEE conference on computer communications workshops, pp 936–941, (2011)

[3]

Barabasi A.L., Albert R., Emergence of scaling in random networks, Science, 286, (1999)

[4]

Gorlitz O., Sizov S., Staab S., Pints: Peer-to-peer infrastructure for tagging systems, In: Proceedings of the 7th international conference on peer-to-peer systems, (2008)

[5]

Guillaume J.L., Latapy M., Bipartite structure of all complex networks, Inf Process Lett, 90, pp. 215-221, (2004)

[6]

Latapy M., Magnien C., Del Vecchio N., Basic notions for the analysis of large two-mode networks, Soc Netw, 30, pp. 31-48, (2008)

[7]

Lind P.G., Gonzalez M.C., Herrmann H.J., Cycles and clustering in bipartite networks, Phys Rev E, 72, 56127, (2005)

[8]

Newman M.E.J., Park J., Why social networks are different from other types of networks, Phys Rev E, 68, 36122, (2003)

[9]

Newman M.E.J., Strogatz S.H., Watts D.J., Random graphs with arbitrary degree distributions and their applications, Phys Rev E, 64, 26118, (2001)

[10]

Prieur C., Cardon D., Beuscart J.S., Pissard N., Pons P., The strength of weak cooperation: a case study on Flickr, Comput Res Repos, (2008)

← 1 2 →