Article

Application of kernels to link analysis

Authors:

Takahiko Ito,

Masashi Shimbo,

Taku Kudo,

Yuji MatsumotoAuthors Info & Claims

KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

Pages 586 - 592

https://doi.org/10.1145/1081870.1081941

Published: 21 August 2005 Publication History

Get Access

Abstract

The application of kernel methods to link analysis is explored. In particular, Kandola et al.'s Neumann kernels are shown to subsume not only the co-citation and bibliographic coupling relatedness but also Kleinberg's HITS importance. These popular measures of relatedness and importance correspond to the Neumann kernels at the extremes of their parameter range, and hence these kernels can be interpreted as defining a spectrum of link analysis measures intermediate between co-citation/bibliographic coupling and HITS. We also show that the kernels based on the graph Laplacian, including the regularized Laplacian and diffusion kernels, provide relatedness measures that overcome some limitations of co-citation relatedness. The property of these kernel-based link analysis measures is examined with a network of bibliographic citations. Practical issues in applying these methods to real data are discussed, and possible solutions are proposed.

References

[1]

S. Brin and L. Page. The anatomy of a large-scale hypertextual (web) search engine. Computer Network and ISDN Systems, 30(1--7):107--117, 1998.

Digital Library

Google Scholar

[2]

F. R. K. Chung. Spectral Graph Theory. Am. Math. Soc., Providence, RI, USA, 1997.

Google Scholar

[3]

R. Fagin, R. Kumar, and D. Sivakumar. Comparing top k lists. SIAM J. Discrete Math., 17(1):134--160, 2003.

Digital Library

Google Scholar

[4]

G. H. Golub and C. F. Van Loan. Matrix Computation. Johns Hopkins Univ. Press, 3rd edition, 1996.

Google Scholar

[5]

J. Kandola, J. Shawe-Taylor, and N. Cristianini. Learning semantic similarity. In NIPS 15, pages 673--680, 2003.

Google Scholar

[6]

M. M. Kessler. Bibliographic coupling between scientific papers. Am. Documentation, 14(1):10--25, 1963.

Crossref

Google Scholar

[7]

J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46:604--632, 1999.

Digital Library

Google Scholar

[8]

R. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In Proc. 18th ICML, pages 21--24, 2001.

Digital Library

Google Scholar

[9]

B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, USA, 2002.

Google Scholar

[10]

M. Shimbo and T. Ito. Application of kernels to link analysis: proofs and additional experimental results. Technical report, Grad. School of Inform. Science, Nara Institute of Science and Technology, 2005. In preparation.

Google Scholar

[11]

H. Small. Co-citation in the scientific literature: a new measure of the relationship between two documents. J. Am. Soc. for Inform. Science, 24:265--269, 1973.

Crossref

Google Scholar

[12]

A. J. Smola and R. Kondor. Kernels and regularization of graphs. In Proc. COLT'03, pages 144--158, 2003.

Crossref

Google Scholar

[13]

S. White and P. Smyth. Algorithms for estimating relative importance in networks. In Proc. KDD'03, pages 266--275, 2003.

Digital Library

Google Scholar

Cited By

View all

Li MCoşkun MKoyutürk MWang MYoon B(2023)Canonical Representation of Biological Networks Using Graph ConvolutionProceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3584371.3612963(1-9)Online publication date: 3-Sep-2023
https://dl.acm.org/doi/10.1145/3584371.3612963
Li CYang QPang BChen TCheng QLiu J(2021)A Mixed Strategy of Higher-Order Structure for Link Prediction Problem on Bipartite GraphsMathematics10.3390/math92431959:24(3195)Online publication date: 10-Dec-2021
https://doi.org/10.3390/math9243195
Devezas JNunes S(2021)A Review of Graph-Based Models for Entity-Oriented SearchSN Computer Science10.1007/s42979-021-00828-w2:6Online publication date: 30-Aug-2021
https://doi.org/10.1007/s42979-021-00828-w
Show More Cited By

Index Terms

Application of kernels to link analysis
1. Information systems
  1. Information retrieval

Recommendations

Link analysis ranking: algorithms, theory, and experiments

The explosive growth and the widespread accessibility of the Web has led to a surge of research activity in the area of information retrieval on the World Wide Web. The seminal papers of Kleinberg [1998, 1999] and Brin and Page [1998] introduced Link ...
On the properties of von Neumann kernels for link analysis

We study the effectiveness of Kandola et al.'s von Neumann kernels as a link analysis measure. We show that von Neumann kernels subsume Kleinberg's HITS importance at the limit of their parameter range. Because they reduce to co-citation relatedness at ...
Topical link analysis for web search
SIGIR '06: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval

Traditional web link-based ranking schemes use a single score to measure a page's authority without concern of the community from which that authority is derived. As a result, a resource that is highly popular for one topic may dominate the results of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

August 2005

844 pages

ISBN:159593135X

DOI:10.1145/1081870

General Chair:
Robert Grossman
University of Illinois at Chicago & Open Data Partners, USA
,
Program Chairs:
Roberto Bayardo
IBM Almaden Research, USA
,
Kristin Bennett
RPI, USA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD05

Sponsor:

KDD05: The Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2005

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
796
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li MCoşkun MKoyutürk MWang MYoon B(2023)Canonical Representation of Biological Networks Using Graph ConvolutionProceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3584371.3612963(1-9)Online publication date: 3-Sep-2023
https://dl.acm.org/doi/10.1145/3584371.3612963
Li CYang QPang BChen TCheng QLiu J(2021)A Mixed Strategy of Higher-Order Structure for Link Prediction Problem on Bipartite GraphsMathematics10.3390/math92431959:24(3195)Online publication date: 10-Dec-2021
https://doi.org/10.3390/math9243195
Devezas JNunes S(2021)A Review of Graph-Based Models for Entity-Oriented SearchSN Computer Science10.1007/s42979-021-00828-w2:6Online publication date: 30-Aug-2021
https://doi.org/10.1007/s42979-021-00828-w
Koutrouli MKaratzas EPaez-Espino DPavlopoulos G(2020)A Guide to Conquer the Biological Network Era Using Graph TheoryFrontiers in Bioengineering and Biotechnology10.3389/fbioe.2020.000348Online publication date: 31-Jan-2020
https://doi.org/10.3389/fbioe.2020.00034
Derr TWang ZDacon JTang J(2020)Link and interaction polarity predictions in signed networksSocial Network Analysis and Mining10.1007/s13278-020-0630-610:1Online publication date: 10-Mar-2020
https://doi.org/10.1007/s13278-020-0630-6
Aghabozorgi FReza Khayyambashi M(2018)A new study of using temporality and weights to improve similarity measures for link prediction of social networksJournal of Intelligent & Fuzzy Systems10.3233/JIFS-1777034:4(2667-2678)Online publication date: 19-Apr-2018
https://doi.org/10.3233/JIFS-17770
Derr TWang ZTang J(2018)Opinions Power Opinions: Joint Link and Interaction Polarity Predictions in Signed Networks2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)10.1109/ASONAM.2018.8508263(363-366)Online publication date: Aug-2018
https://doi.org/10.1109/ASONAM.2018.8508263
Satheesh MRemya G(2017)Collaborative filtering using graph kernel and boosting2017 International Conference on Computational Intelligence in Data Science(ICCIDS)10.1109/ICCIDS.2017.8272658(1-4)Online publication date: Jun-2017
https://doi.org/10.1109/ICCIDS.2017.8272658
Françoisse KKivimäki IMantrach ARossi FSaerens M(2017)A bag-of-paths framework for network data analysisNeural Networks10.1016/j.neunet.2017.03.01090(90-111)Online publication date: Jun-2017
https://doi.org/10.1016/j.neunet.2017.03.010
Sommer FFouss FSaerens M(2017)Modularity-Driven Kernel k-means for Community DetectionArtificial Neural Networks and Machine Learning – ICANN 201710.1007/978-3-319-68612-7_48(423-433)Online publication date: 25-Oct-2017
https://doi.org/10.1007/978-3-319-68612-7_48
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Link analysis ranking: algorithms, theory, and experiments

On the properties of von Neumann kernels for link analysis

Topical link analysis for web search