AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Combining Topological Properties and Strong Ties for Link Prediction

Fulan Qian( ), Yang Gao, Shu Zhao, Jie Tang, Yanping Zhang
School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Center of Information Support & Assurance Technology, Anhui University, Hefei 230601, China.
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China.
Show Author Information

Abstract

Link prediction is an important task that estimates the probability of there being a link between two disconnected nodes. The similarity-based algorithm is a very popular method that employs the node similarities to find links. Most of these types of algorithms focus only on the contribution of common neighborhoods between two nodes. In sociological theory relationships within three degrees are the strong ties that can trigger social behaviors. Thus, strong ties can provide more connection opportunities for unconnected nodes in the networks. As critical topological properties in networks, nodes degrees and node clustering coefficients are well-suited for describing the tightness of connections between nodes. In this paper, we characterize node similarity by utilizing the strong ties of the ego network (i.e., paths within three degrees) and its close connections (node degrees and node clustering coefficients). We propose a link prediction algorithm that combines topological properties with strong ties, which we called the TPSR algorithm. This algorithm includes TPSR2, TPSR3, and the TPSR4 indices. We evaluate the performance of the proposed algorithm using the metrics of precision and the Area Under the Curve (AUC). Our experimental results show the TPSR algorithm to perform remarkably better than others.

Keywords

link predictioncomplex networksstrong tiestopological properties

References

[1]
Fouss F., Yen L., Pirotte A., and Saerens M., An experimental investigation of graph kernels on a collaborative recommendation task, in International Conference on Data Mining, 2006.
Crossref
[2]
Yang Y., Hao G., Tian T., and Li H., Link prediction in brain networks based on a hierarchical random graph model, Tsinghua Sciece and Technology, vol. 20, no. 3, pp. 306-315, 2015.
Crossref Google Scholar
[3]
Costa L. da F., Rodrigues F. A., Travieso G., and Villas Boas P. R., Characterization of complex networks: A survey of measurements, Advances in Physics, vol. 56, no. 1, pp. 167-242, 2010.
Crossref Google Scholar
[4]
Lü L. and Zhou T., Link prediction in complex networks: A survey, Physica A Statistical Mechanics & Its Applications, vol. 390, no. 6, pp. 1150-1170, 2011.
Crossref Google Scholar
[5]
Lorrain F. and White H. C., Structural equivalence of individuals in social networks, The Journal of Mathematical Sociology, vol. 1, no. 1, pp. 49-80, 1971.
Crossref Google Scholar
[6]
Jaccard P., Etude comparative de la distribution florale dans une portion des Alpes et du Jura, Bulletin de la Société Vaudoise des Sciences Naturelles, no. 37, pp. 547-579, 1901.
Google Scholar
[7]
Adamic L. A. and Adar E., Friends and neighbors on the web, Social Networks, vol. 25, no. 3, pp. 211-230, 2003.
Crossref Google Scholar
[8]
Zhou T., Lü L., and Zhang Y. C., Predicting missing links via local information, The European Physical Journal B, vol. 71, no. 4, pp. 623-630, 2009.
Crossref Google Scholar
[9]
Zhang W. and Wu B., Accurate and fast link prediction in complex networks, in International Conference on Natural Computation, 2014.
Crossref
[10]
Wu Z., Lin Y., Wang J., Gregory S., Link prediction with node clustering coefficient, Physica A Statistical Mechanics & Its Applications, vol. 452, pp. 1-8, 2016.
Crossref Google Scholar
[11]
Wu Z., Lin Y., and Zhao Y., A parameter free similarity index based on clustering ability for link prediction in complex networks, arXiv preprint arXiv: 1504.01018, 2015.
[12]
Katz L., A new status index derived from sociometric analysis, Psychometrika, vol. 18, no. 1, pp. 39-43, 1953.
Crossref Google Scholar
[13]
Lü L., Jin C. H., and Zhou T., Similarity index based on local paths for link prediction of complex networks, Physical Review E, vol. 80, no. 4, p. 046122, 2009.
Crossref Google Scholar
[14]
Liu W. and Lü L, Link prediction based on local random walk, Europhysics Letters, vol. 89, no. 5, p. 58007, 2010.
Crossref Google Scholar
[15]
Papadimitriou A., Symeonidis P., and Manolopoulos Y., Fast and accurate link prediction in social networking systems, Journal of Systems and Software, vol. 85, no. 9, pp. 2119-2132, 2012.
Crossref Google Scholar
[16]
Khosravi-Farsani H., Nematbakhsh M., and Lausen G., SRank: Shortest paths as distance between nodes of a graph with application to RDF clustering, Journal of Information Science, vol. 39, no. 2, pp. 198-210, 2013.
Crossref Google Scholar
[17]
Walker S. K., Connected: The surprising power of our social networks and how they shape our lives, Journal of Family Theory & Review, vol. 3, no. 3, pp. 220-224, 2011.
Crossref Google Scholar
[18]
Christakis N. A. and Fowler J. H., Social contagion theory: Examining dynamic social networks and human behavior, Statistics in Medicine, vol. 32, no. 4, pp. 556-577, 2013.
Crossref Google Scholar
[19]
Arney C., Connected: The surprising power of our social networks and how they shape our lives-how your friends’ friends’ friends affect everything you feel, think, and do, Mathematics and Computer Education, vol. 48, no. 2, p. 201, 2014.
Google Scholar
[20]
Lei W. H., Yang Q., and Wang H., Positive influence maximization algorithm based on three degrees of influence, in International Conference on Intelligent Data Engineering and Automated Learning, 2016.
Crossref
[21]
Gong M., Song C., Duan C., and Ma L., An efficient memetic algorithm for influence maximization in social networks, IEEE Computational Intelligence Magazine, vol. 11, no. 3, pp. 22-33, 2016.
Crossref Google Scholar
[22]
Ma H., Yang H., Lyu M. R., and King I., SoRec: Social recommendation using probabilistic matrix factorization, in ACM Conference on Information and Knowledge Management, CIKM 2008, Napa Valley, CA, USA, 2008.
Crossref
[23]
Ma H., Zhou D., Liu C., Lyu M. R., and King I., Recommender systems with social regularization, in Forth International Conference on Web Search and Web Data Mining, WSDM 2011, Hong Kong, China, 2011.
Crossref
[24]
Jamali M. and Ester M., A matrix factorization technique with trust propagation for recommendation in social networks, in ACM Conference on Recommender Systems, Recsys 2010, Barcelona, Spain, 2010.
Crossref
[25]
Milgram S., The small world problem, Psychology Today, vol. 2, no. 1, pp. 60-67, 1967.
Crossref Google Scholar
[26]
Hanley J. A. and Mcneil B. J., A method of comparing the areas under receiver operating characteristic curves derived from the same cases, Radiology, vol. 148, no. 3, pp. 839-843, 1983.
Crossref Google Scholar
[27]
Herlocker J. L., Konstan J. A., Terveen L. G., and Riedl J. T., Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems, vol. 22, no. 1, pp. 5-53, 2004.
Crossref Google Scholar
[28]
Watts D. J. and Strogatz S. H., Collective dynamics of “smallworld” networks, Nature, vol. 393, no. 6684, pp. 440-442, 1998.
Crossref Google Scholar
[29]
Newman M. E. J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, vol. 74, p. 036104, 2006.
Crossref Google Scholar
[30]
Gleiser B. P. and Danon L., Community structure in jazz, Advances in Complex Systems, vol. 6, no. 4, p. 565, 2003.
Crossref Google Scholar
[31]
Li L., Qian L., Cheng J., Ma M., Chen X., Accurate similarity index based on the contributions of paths and end nodes for link prediction, Journal of Information Science, vol. 41, no. 2, pp. 167-177, 2014.
Crossref Google Scholar
[32]
Ulanowicz R. E., Heymans J. J., and Egnotovich M. S., Network analysis of trophic dynamics in South Florida ecosystems, in Proceedings of South Florida Restoration Science Forum, 1999.
[33]
Baird D., Luczkovich J., and Christian R. R., Assessment of spatial and temporal variability in ecosystem attributes of the St Marks National Wildlife Refuge, Apalachee Bay, Florida, Estuarine Coastal & Shelf Science, vol. 47, no. 3, pp. 329-349, 1998.
Crossref Google Scholar
[34]
Li F., He J., Huang G., Zhang Y., Shi Y., and Zhou R., Nodecoupling clustering approaches for link prediction, Knowledge-Based Systems, vol. 89, pp. 669-680, 2015.
Crossref Google Scholar
[35]
Adamic L. A. and Glance N., The political blogosphere and the 2004 U.S. election: Divided they blog, in Proceedings of the 3rd International Workshop on Link Discovery, 2005.
Crossref
[36]
Lü L., Pan L., Zhou T., Zhang Y. C., and Stanley H. E., Toward link predictability of complex networks, Proceedings of the National Academy of Sciences, vol. 112, no. 8, pp. 2325-2330, 2015.
Crossref Google Scholar
[37]
Menon A. K. and Elkan C., Link prediction via matrix factorization, in European Conference on Machine Learning and Knowledge Discovery in Databases, 2011.
Crossref
[38]
Lü L. and Zhou T., Role of weak ties in link prediction of complex networks, in ACM International Workshop on Complex Networks Meet Information & Knowledge Management, 2009.
[39]
von Mering C., Krause R., Snel B., Cornell M., Oliver S. G., Fields S., and Bork P., Comparative assessment of largescale data sets of protein-protein interactions, Nature, vol. 417, no. 6887, pp. 399-403, 2002.
Crossref Google Scholar
[40]
Newman M. E. and Watts D. J., Renormalization group analysis of the small-world network model, Physics Letters A, vol. 263, no. 4, pp. 341-346, 1999.
Crossref Google Scholar
[41]
Wang P., Xu B., Wu Y., and Zhou X., Link prediction in social networks: The state-of-the-art, Science China Information Sciences, vol. 58, no. 1, pp. 1-38, 2014.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 22 Issue 6,
December 2017
Pages 595-608
DOI: 10.23919/TST.2017.8195343
Cite this article:
Qian F, Gao Y, Zhao S, et al. Combining Topological Properties and Strong Ties for Link Prediction. Tsinghua Science and Technology, 2017, 22(6): 595-608. https://doi.org/10.23919/TST.2017.8195343

639

Views

23

Downloads

8

Crossref

N/A

Web of Science

8

Scopus

0

CSCD

Altmetrics
Received: 03 January 2017
Revised: 17 June 2017
Accepted: 19 June 2017
Published: 14 December 2017
© The author(s) 2017
Return