×

Potential links by neighbor communities. (English) Zbl 1402.91644

Summary: The probability of two nodes to be linked is related to their similarities in the network. Based on statistical inference, a network-structure similarity index, therefore, is proposed to find the potential links. This index quantifies the effects of the node communities on these links. And an algorithm for the index is also successfully designed. The experiments on several networks with ground-truth groups and temporal attributes reveal that two nodes are likely to be connected if some of their neighbor nodes are in common communities. The results from these experiments with tested networks, several of which cover more than a million nodes, show the reliability of the index and the advantage of its algorithm.

MSC:

91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Liben-Nowell, D.; Kleinberg, J., In CIKM ’03: conference on information and knowledge management, 556-559, (2003), ACM New York, NY,USA
[2] Lu, L.; Zhou, T., Physica A, 390, 1150, (2011)
[3] Adamic, L. A.; Adar, E., Soc. Netw., 25, 211, (2003)
[4] Newman, M. E.J., Phys. Rev. E, 64, (2001), 025102
[5] Katz, L., Psychometrika, 18, 39, (1953)
[6] Yan, B.; Gregory, S., Phys. Rev. E, 85, (2012), 056112
[7] Guimera, R.; Sales-Pardo, M., Proc. Natl. Acad. Sci., 106, 22073, (2009)
[8] Zhang, X., Physica A, 393, 553-559, (2014)
[9] Clauset, A.; Moore, C.; Newman, M. E.J., Nature, 453, 98, (2008)
[10] Newman, M. E.J.; Leicht, E. A., Proc. Natl. Acad. Sci., 104, 9564-9569, (2007)
[11] Karrer, B.; Newman, M. E.J., Phys. Rev. E, 83, (2011), 016107
[12] Blondel, V. D.; Guillaume, J. L.; Lambiotte, R.; Lefebvre, E., J. Stat. Mech., 83, P10008, (2008)
[13] Gregory, S., J. Stat. Mech., P02017, (2011)
[14] Hand, D. J.; Till, R. J., Mach. Learn., 45, 171-186, (2001)
[15] Newman, M. E.J., Proc. Natl. Acad. Sci., 98, 404-409, (2001)
[16] M. Ley, S. Dagstuhl, DBLP Dataset Available at http://dblp.uni-trier.de/xml/dblp.
[17] Yang, J.; Leskovec, J., ICDM, (2012)
[18] Leskovec, J.; Lang, K.; Dasgupta, A.; Mahoney, M., Internet Math., 6, 29-123, (2009)
[19] Klimmt, B.; Yang, Y., CEAS, (2004)
[20] Leskovec, J.; Kleinberg, J.; Faloutsos, C., ACM TKDD, 1, (2007)
[21] Leskovec, J.; Huttenlocher, D.; Kleinberg, J., CHI, (2010)
[22] Leskovec, J.; Huttenlocher, D.; Kleinberg, J., WWW, (2010)
[23] Backstrom, L.; Huttenlocher, D.; Kleinberg, J.; Lan, X., KDD, (2006)
[24] Newman, M. E.J., Phys. Rev. E, 74, 3, (2006), 036104
[25] Watts, D. J.; Strogatz, S. H., Nature, 393, 440-442, (1998)
[26] Rosvall, M.; Bergstrom, C. T., Proc. Natl. Acad. Sci., 105, 1118, (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.