Random hypergraphs and their applications

被引:174
作者
Ghoshal, Gourab [1 ,2 ]
Zlatic, Vinko [3 ,4 ]
Caldarelli, Guido [4 ,5 ]
Newman, M. E. J. [1 ,6 ,7 ]
机构
[1] Univ Michigan, Dept Phys, Ann Arbor, MI 48109 USA
[2] Univ Michigan, Michigan Ctr Theoret Phys, Ann Arbor, MI 48109 USA
[3] Rudjer Boskovic Inst, Div Theoret Phys, HR-10002 Zagreb, Croatia
[4] Univ Roma La Sapienza, Dipartimento Fis, CNR, INFM,Ctr SMC, I-00185 Rome, Italy
[5] Linkalab Complex Syst Computat Lab, I-09100 Cagliari, Italy
[6] Univ Michigan, Ctr Study Complex Syst, Ann Arbor, MI 48109 USA
[7] Santa Fe Inst, Santa Fe, NM 87501 USA
基金
美国国家科学基金会;
关键词
complex networks; graph theory; EVOLUTION;
D O I
10.1103/PhysRevE.79.066118
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
In the last few years we have witnessed the emergence, primarily in online communities, of new types of social networks that require for their representation more complex graph structures than have been employed in the past. One example is the folksonomy, a tripartite structure of users, resources, and tags-labels collaboratively applied by the users to the resources in order to impart meaningful structure on an otherwise undifferentiated database. Here we propose a mathematical model of such tripartite structures that represents them as random hypergraphs. We show that it is possible to calculate many properties of this model exactly in the limit of large network size and we compare the results against observations of a real folksonomy, that of the online photography website Flickr. We show that in some cases the model matches the properties of the observed network well, while in others there are significant differences, which we find to be attributable to the practice of multiple tagging, i.e., the application by a single user of many tags to one resource or one tag to many resources.
引用
收藏
页数:10
相关论文
共 22 条
  • [1] Abramowitz M., 1970, HDB MATH FUNCTIONS
  • [2] Complex networks: Structure and dynamics
    Boccaletti, S.
    Latora, V.
    Moreno, Y.
    Chavez, M.
    Hwang, D. -U.
    [J]. PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2006, 424 (4-5): : 175 - 308
  • [3] Bollobas, 2001, RANDOM GRAPHS, DOI 10.1017/CBO9780511814068
  • [4] Caldarelli G., 2007, SCALE FREE NETWORKS
  • [5] Cattuto C, 2007, AI COMMUN, V20, P245
  • [6] QUASI-RANDOM HYPERGRAPHS
    CHUNG, FRK
    GRAHAM, RL
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1989, 86 (21) : 8175 - 8177
  • [7] The cores of random hypergraphs with a given degree sequence
    Cooper, C
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2004, 25 (04) : 353 - 375
  • [8] FINITE SIZE SCALING FOR THE CORE OF LARGE RANDOM HYPERGRAPHS
    Dembo, Amir
    Montanar, Andrea
    [J]. ANNALS OF APPLIED PROBABILITY, 2008, 18 (05) : 1993 - 2040
  • [9] Evolution of networks
    Dorogovtsev, SN
    Mendes, JFF
    [J]. ADVANCES IN PHYSICS, 2002, 51 (04) : 1079 - 1187
  • [10] Erdo P., 1975, Infinite and Finite Sets, P609