research-article

sonLP: social network link prediction by principal component regression

Authors:

Y. C. TayAuthors Info & Claims

ASONAM '13: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Pages 364 - 371

https://doi.org/10.1145/2492517.2492558

Published: 25 August 2013 Publication History

Abstract

Social networks are driven by social interaction and therefore dynamic. When modeled as a graph, nodes and links are continually added and deleted, and there is considerable interest in social network analysis on predicting link formation. Current work has not adequately addressed three issues:

(1) Most link predictors start with using features from the link topology as input. How do features in other dimensions of the social network data affect link formation? (2) The dynamic nature of social networks implies the features driving link formation are constantly changing. How can a predictor automatically select the features that are important for link formation? (3) Node pairs that are not linked can outnumber links by orders of magnitude, but previous work do not address this imbalance. How can we design a predictor that is robust with respect to link imbalance?

This paper presents sonLP, a social network link predictor. It uses principal component analysis to identify features that are important to link prediction, its tradeoff between true and false positives is near optimal for a wide range of link imbalance, and it has optimal time complexity. Experiments with coauthorship prediction in the ACM researcher community also show the importance of using features outside the links' dimension.

References

[1]

L. A. Adamic and E. Adar. Friends and neighbors on the web. SOCIAL NETWORKS, 25: 211--230, 2001.

[2]

L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proc. WSDM, pages 635--644, 2011.

Digital Library

[3]

J. R. Doppa, J. Yu, P. Tadepalli, and L. Getoor. Chance-constrained programs for link prediction. Proc. Workshop on Analyzing Networks and Learning with Graphs (NIPS-2009).

[4]

M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici. Link prediction in social networks using computationally efficient topological features. In SocialCom/PASSAT, pages 73--80, 2011.

[5]

A. Halevy, P. Norvig, and F. Pereira. The unreasonable effectiveness of data. IEEE Intelligent Systems, 24: 8--12, 2009.

Digital Library

[6]

M. Hall, E. Frank, G. Holmes, et al. The weka data mining software: an update. SIGKDD Explor. Newsl., 11(1): 10--18, 2009.

Digital Library

[7]

M. A. Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction using supervised learning. In Proc. of SDM 06 Workshop on Link Analysis, Counterterrorism and Security, 2006.

[8]

M. A. Hasan and M. J. Zaki. A survey of link prediction in social networks. In Social Network Data Analytics, pages 243--275. 2011.

[9]

J. Huang, Z. Zhuang, J. Li, and C. L. Giles. Collaboration over time: characterizing and modeling network evolution. In Proc. WSDM, pages 107--116, 2008.

Digital Library

[10]

D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proc. CIKM, pages 556--559, 2003.

Digital Library

[11]

R. N. Lichtenwalter, J. T. Lussier, and N. V. Chawla. New perspectives and methods in link prediction. In Proc. KDD, pages 243--252, 2010.

Digital Library

[12]

Y. Lu, I. Cohen, X. S. Zhou, and Q. Tian. Feature selection using principal feature analysis. In MULTIMEDIA, pages 301--304, 2007.

Digital Library

[13]

Z. Lu, B. Savas, W. Tang, and I. S. Dhillon. Supervised link prediction using multiple sources. In Proc. ICDM, pages 923--928, 2010.

Digital Library

[14]

D. Pennock, G. Flake, S. Lawrence, E. Glover, and C. Giles. Winners don't take all: Characterizing the competition for links on the web. Proceedings of the National Academy of Sciences, 99(8), 2002.

[15]

R. Popescul and L. H. Ungar. Statistical relational learning for link prediction. In In Proc. Workshop on Learning Statistical Models from Relational Data at IJCAI-2003, 2003.

[16]

A. Potgieter, K. April, R. Cooke, and I. Osunmakinde. Temporality in link prediction: Understanding social complexity. Sprouts: Working Papers on Information Systems, 7(9), 2007.

[17]

M. J. Rattigan and D. Jensen. The case for anomalous link discovery. SIGKDD Explor. Newsl., 7(2): 41--47, Dec. 2005.

Digital Library

[18]

F. Reitz and O. Hoffmann. An analysis of the evolving coverage of computer science sub-fields in the DBLP digital library. In Proc. ECDL, pages 216--227, 2010.

Digital Library

[19]

P. Reuther, B. Walter, M. Ley, A. Weber, and S. Klink. Managing the quality of person names in DBLP. In Proc. European Conf. Research and Advanced Technology for Digital Libraries, pages 508--511, 2006.

Digital Library

[20]

G. Rossetti, M. Berlingerio, and F. Giannotti. Scalable link prediction on multidimensional networks. In Proc. ICDMW, pages 979--986, 2011.

Digital Library

[21]

A. Sharma and K. K. Paliwal. Fast principal component analysis using fixed-point algorithm. Pattern Recogn. Lett., 28(10): 1151--1155, 2007.

Digital Library

[22]

Y. Sun, R. Barber, M. Gupta, C. C. Aggarwal, and J. Han. Co-author relationship prediction in heterogeneous bibliographic networks. In Proc. ASONAM, pages 121--128, 2011.

Digital Library

[23]

T. Tylenda, R. Angelova, and S. Bedathur. Towards time-aware link prediction in evolving social networks. In Proc. SNA-KDD, pages 9:1--9:10, 2009.

Digital Library

[24]

C. Wang, V. Satuluri, and S. Parthasarathy. Local probabilistic models for link prediction. In Proc. ICDM, pages 322--331, 2007.

Digital Library

[25]

Z. Xu, V. Tresp, S. Yu, and K. Yu. Nonparametric relational learning for social network analysis. In Proc. SNA-KDD, 2008.

Cited By

Pujari MKanawati R(2020)Link Prediction in Complex NetworksCognitive Analytics10.4018/978-1-7998-2460-2.ch061(1196-1236)Online publication date: 2020
https://doi.org/10.4018/978-1-7998-2460-2.ch061
Gao MChen LLi BLiu W(2018)A link prediction algorithm based on low-rank matrix completionApplied Intelligence10.1007/s10489-018-1220-448:12(4531-4550)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10489-018-1220-4
Shakibian HCharkari NJalili S(2018)Multi-kernel one class link prediction in heterogeneous complex networksApplied Intelligence10.1007/s10489-018-1157-748:10(3411-3428)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10489-018-1157-7
Show More Cited By

Index Terms

sonLP: social network link prediction by principal component regression
1. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
      1. Web-based interaction
2. Information systems
  1. Information retrieval
    1. Document representation
  2. Information systems applications
    1. Data mining

Recommendations

Friendship Maintenance and Prediction in Multiple Social Networks
HT '16: Proceedings of the 27th ACM Conference on Hypertext and Social Media

Due to the proliferation of online social networks (OSNs), users find themselves participating in multiple OSNs. These users leave their activity traces as they maintain friendships and interact with other users in these OSNs. In this work, we analyze ...
Integrated anchor and social link predictions across multiple social networks

In recent years, various online social networks offering specific services have gained great popularity and success. To enjoy more online social services, some users can be involved in multiple social networks simultaneously. A challenging problem in ...
Learning to predict reciprocity and triadic closure in social networks

We study how links are formed in social networks. In particular, we focus on investigating how a reciprocal (two-way) link, the basic relationship in social networks, is developed from a parasocial (one-way) relationship and how the relationships ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '13: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

August 2013

1558 pages

ISBN:9781450322409

DOI:10.1145/2492517

General Chairs:
Jon Rokne
University of Calgary, Calgary, AB, Canada
,
Christos Faloutsos
Carnegie Mellon University, Pittsburgh, PA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Education - Singapore

Conference

ASONAM '13

Sponsor:

SIGKDD

ASONAM '13: Advances in Social Networks Analysis and Mining 2013

August 25 - 28, 2013

Ontario, Niagara, Canada

Acceptance Rates

Overall Acceptance Rate 116 of 549 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pujari MKanawati R(2020)Link Prediction in Complex NetworksCognitive Analytics10.4018/978-1-7998-2460-2.ch061(1196-1236)Online publication date: 2020
https://doi.org/10.4018/978-1-7998-2460-2.ch061
Gao MChen LLi BLiu W(2018)A link prediction algorithm based on low-rank matrix completionApplied Intelligence10.1007/s10489-018-1220-448:12(4531-4550)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10489-018-1220-4
Shakibian HCharkari NJalili S(2018)Multi-kernel one class link prediction in heterogeneous complex networksApplied Intelligence10.1007/s10489-018-1157-748:10(3411-3428)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10489-018-1157-7
Tajeuna EBouguessa MWang SShin SShin DLencastre M(2017)Survival analysis for modeling critical events that communities may undergo in dynamic social networksProceedings of the Symposium on Applied Computing10.1145/3019612.3019817(1068-1075)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3019612.3019817
Dai CChen LLi BLi Y(2017)Link prediction in multi-relational networks based on relational similarityInformation Sciences: an International Journal10.1016/j.ins.2017.02.003394:C(198-216)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.ins.2017.02.003
Gao MChen LLi BLi YLiu WXu Y(2017)Projection-based link prediction in a bipartite networkInformation Sciences: an International Journal10.1016/j.ins.2016.10.015376:C(158-171)Online publication date: 10-Jan-2017
https://dl.acm.org/doi/10.1016/j.ins.2016.10.015
Dai CChen LLi B(2017)Link prediction based on sampling in complex networksApplied Intelligence10.1007/s10489-016-0872-147:1(1-12)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10489-016-0872-1
Caiyan DChen LLi B(2017)Link prediction in complex network based on modularitySoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2030-421:15(4197-4214)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00500-016-2030-4
Pujari MKanawati R(2016)Link Prediction in Complex NetworksAdvanced Methods for Complex Network Analysis10.4018/978-1-4666-9964-9.ch003(58-97)Online publication date: 2016
https://doi.org/10.4018/978-1-4666-9964-9.ch003
Ahmed NChen LWang YLi BLi YLiu W(2016)Sampling-based algorithm for link prediction in temporal networksInformation Sciences: an International Journal10.1016/j.ins.2016.09.029374:C(1-14)Online publication date: 20-Dec-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.09.029
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents