poster

Modeling evolution of a social network using temporalgraph kernels

Authors:

Sanasam Ranbir SinghAuthors Info & Claims

SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

Pages 1051 - 1054

https://doi.org/10.1145/2600428.2609507

Published: 03 July 2014 Publication History

Abstract

Majority of the studies on modeling the evolution of a social network using spectral graph kernels do not consider temporal effects while estimating the kernel parameters. As a result, such kernels fail to capture structural properties of the evolution over the time. In this paper, we propose temporal spectral graph kernels of four popular graph kernels namely path counting, triangle closing, exponential and neumann. Their responses in predicting future growth of the network have been investigated in detail, using two large datasets namely Facebook and DBLP. It is evident from various experimental setups that the proposed temporal spectral graph kernels outperform all of their non-temporal counterparts in predicting future growth of the networks.

References

[1]

S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borgwardt. Graph kernels. J. Mach. Learn. Res., 11:1201--1242, Aug. 2010.

Digital Library

[2]

R. I. Kondor and J. D. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In Proc. of the Nineteenth International Conference on Machine Learning, ICML '02, pages 315--322, San Francisco, CA, USA, 2002.

Digital Library

[3]

A. Smola and R. Kondor. Kernels and regularization on graphs. In Proc. Conf. on Learning Theory and Kernel Machines, pages 144--158, 2003.

[4]

F. Fouss, L. Yen, A. Pirotte, and M. Saerens. An experimental investigation of graph kernels on a collaborative recommendation task. In Proc. Int. Conf. on Data Mining, pages 863--868, 2006.

Digital Library

[5]

D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol., 58(7):1019--1031, May 2007.

Digital Library

[6]

B. M. Sarwar, G. Karypis, J. A. Konstan, and J. T. Riedl. Application of dimensionality reduction in recommender system -- a case study. In IN ACM WEBKDD WORKSHOP, 2000.

[7]

A. K. Menon and C. Elkan. Link prediction via matrix factorization. In Proc. of the 2011 European conference on Machine learning and knowledge discovery in databases - Volume Part II, ECML PKDD'11, pages 437--452, Berlin, Heidelberg, 2011.

Digital Library

[8]

J. Kunegis, D. Fay, and C. Bauckhage. Network growth and the spectral evolution model. In Proc. of the 19th ACM international conference on Information and knowledge management, CIKM '10, pages 739--748, New York, NY, USA, 2010. ACM.

Digital Library

[9]

T. Thorne and M. P. H. Stumpf. Graph spectral analysis of protein interaction network evolution. Journal of The Royal Society Interface, May 2012.

[10]

S. Sarkar and A. Dong. Community detection in graphs using singular value decomposition. Phys. Rev. E, 83:046114, Apr 2011.

[11]

S. G. Matus Medo, Giulio Cimini. Temporal effects in the growth of networks. Physical Review Letters, 2011.

[12]

D. M. Dunlavy, T. G. Kolda, and E. Acar. Temporal link prediction using matrix and tensor factorizations. ACM Trans. Knowl. Discov. Data, 5(2):10:1--10:27, Feb. 2011.

Digital Library

[13]

J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In Proc. of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '08, pages 462--470, New York, NY, USA, 2008. ACM.

Digital Library

[14]

L. Lü, C. Jin, and T. Zhou. Similarity index based on local paths for link prediction of complex networks. Physical Review E, 80(4):046122, 2009.

[15]

F. Chung. Spectral Graph Theory. American Math. Society, 1997.

[16]

P. R. Dragos Cvetkovic and S. Simic. Eigenspaces of Graphs. Cambridge University Press, 1997.

[17]

Dblp dataset, 2012. http://dblp.uni-trier.de/.

[18]

A. Mislove, M. Cha, B. Viswanath, and K. P.Gummadi. On the evolution of user interaction in facebook. In Proc. of the 2nd ACM workshop on Online social networks,Aug.2009

Digital Library

Cited By

Anil AKumar DSharma SSingha RSarmah RBhattacharya NSingh S(2015)Link Prediction Using Social Network Analysis over Heterogeneous Terrorist Network2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity)10.1109/SmartCity.2015.82(267-272)Online publication date: Dec-2015
https://doi.org/10.1109/SmartCity.2015.82

Index Terms

Modeling evolution of a social network using temporalgraph kernels
1. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
      1. Clustering and classification
  2. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

Network growth and the spectral evolution model
CIKM '10: Proceedings of the 19th ACM international conference on Information and knowledge management

We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graph's spectrum, ...
Fast depth-based subgraph kernels for unattributed graphs

In this paper, we investigate two fast subgraph kernels based on a depth-based representation of graph-structure. Both methods gauge depth information through a family of K-layer expansion subgraphs rooted at a vertex 1. The first method commences by ...
Spectral evolution in dynamic networks

We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graph's spectrum, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

July 2014

1330 pages

ISBN:9781450322577

DOI:10.1145/2600428

General Chairs:
Shlomo Geva
Queensland University of Technology
,
Andrew Trotman
University of Dunedin
,
Program Chairs:
Peter Bruza
Queensland University of Technology
,
Charles L.A. Clarke
University of Waterloo
,
Kal Järvelin
University of Tampere

Copyright © 2014 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

SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

SIGIR '14

Sponsor:

SIGIR

SIGIR '14: The 37th International ACM SIGIR Conference on Research and Development in Information Retrieval

July 6 - 11, 2014

Queensland, Gold Coast, Australia

Acceptance Rates

SIGIR '14 Paper Acceptance Rate 82 of 387 submissions, 21%;

Overall Acceptance Rate 792 of 3,983 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
473
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anil AKumar DSharma SSingha RSarmah RBhattacharya NSingh S(2015)Link Prediction Using Social Network Analysis over Heterogeneous Terrorist Network2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity)10.1109/SmartCity.2015.82(267-272)Online publication date: Dec-2015
https://doi.org/10.1109/SmartCity.2015.82

View Options

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