Skip to main content
Erschienen in: Social Network Analysis and Mining 4/2013

01.12.2013 | Original Article

Fast recommendation on bibliographic networks with sparse-matrix ordering and partitioning

verfasst von: Onur Küçüktunç, Kamer Kaya, Erik Saule, Ümit V. Çatalyürek

Erschienen in: Social Network Analysis and Mining | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Graphs and matrices are widely used in algorithms for social network analyses. Since the number of interactions is much less than the possible number of interactions, the graphs and matrices used in the analyses are usually sparse. In this paper, we propose an efficient implementation of a sparse-matrix computation which arises in our publicly available citation recommendation service theadvisor as well as in many other recommendation systems. The recommendation algorithm uses a sparse matrix generated from the citation graph. We observed that the nonzero pattern of this matrix is highly irregular and the computation suffers from high number of cache misses. We propose techniques for storing the matrix in memory efficiently and we reduced the number of cache misses with ordering and partitioning. Experimental results show that our techniques are highly efficient in reducing the query processing time which is highly crucial for a web service.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Fußnoten
2
The Katz centrality of a node i can be computed as \({\rm Katz}(i) = \sum\nolimits_{j=1}^n {\rm Katz}(i,j) = \sum\nolimits_{j=1}^n\sum\nolimits_{\ell = 1}^\infty \beta^\ell (A^\ell)_{ji}\) where A is the 0–1 adjacency matrix of the citation graph. When β is smaller than the reciprocal of the largest eigenvalue, the Katz centralities can be computed as \(((I - \beta A^T)^{-1} -I )\buildrel{\rightarrow} \over {I}\) where I is the identity matrix and \(\buildrel{\rightarrow} \over {I}\) is the identity vector.
 
Literatur
Zurück zum Zitat Agarwal RC, Gustavson FG, Zubair M (1992) A high performance algorithm using pre-processing for the sparse matrix-vector multiplication. In: Proceedings of ACM/IEEE Supercomputing, pp 32–41 Agarwal RC, Gustavson FG, Zubair M (1992) A high performance algorithm using pre-processing for the sparse matrix-vector multiplication. In: Proceedings of ACM/IEEE Supercomputing, pp 32–41
Zurück zum Zitat Akbudak K, Kayaaslan E, Aykanat C (2012) Hypergraph-partitioning-based models and methods for exploiting cache locality in sparse-matrix vector multiplication. CoRR abs/1202.3856 Akbudak K, Kayaaslan E, Aykanat C (2012) Hypergraph-partitioning-based models and methods for exploiting cache locality in sparse-matrix vector multiplication. CoRR abs/1202.3856
Zurück zum Zitat Amestoy PR, Davis TA, Duff IS (1996) An approximate minimum degree ordering algorithm. SIAM J Matrix Anal Appl 17(4):886–905MathSciNetCrossRefMATH Amestoy PR, Davis TA, Duff IS (1996) An approximate minimum degree ordering algorithm. SIAM J Matrix Anal Appl 17(4):886–905MathSciNetCrossRefMATH
Zurück zum Zitat Bollen J, Rodriguez MA, de Sompel HV (2006) Journal status. Scientometrics 69(3):669–687CrossRef Bollen J, Rodriguez MA, de Sompel HV (2006) Journal status. Scientometrics 69(3):669–687CrossRef
Zurück zum Zitat Buluç A, Williams S, Oliker L, Demmel J (2011) Reduced-bandwidth multithreaded algorithms for sparse matrix-vector multiplication. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium, pp 721–733 Buluç A, Williams S, Oliker L, Demmel J (2011) Reduced-bandwidth multithreaded algorithms for sparse matrix-vector multiplication. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium, pp 721–733
Zurück zum Zitat Çatalyürek ÜV, Aykanat C (1999) Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans Parallel Distrib Syst 10:673–693CrossRef Çatalyürek ÜV, Aykanat C (1999) Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans Parallel Distrib Syst 10:673–693CrossRef
Zurück zum Zitat Çatalyürek ÜV, Aykanat C (2001) A fine-grain hypergraph model for 2D decomposition of sparse matrices. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium Çatalyürek ÜV, Aykanat C (2001) A fine-grain hypergraph model for 2D decomposition of sparse matrices. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium
Zurück zum Zitat Chipman KC, Singh AK (2009) Predicting genetic interactions with random walks on biological networks. BMC Bioinformatics 10:17CrossRef Chipman KC, Singh AK (2009) Predicting genetic interactions with random walks on biological networks. BMC Bioinformatics 10:17CrossRef
Zurück zum Zitat Cuthill E, McKee J (1969) Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of ACM national conference, pp 157–172 Cuthill E, McKee J (1969) Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of ACM national conference, pp 157–172
Zurück zum Zitat Gori, M. Pucci A (2006) Research paper recommender systems: a random-walk based approach. In: Proceedings of IEEE/WIC/ACM Web Intelligence, pp 778–781 Gori, M. Pucci A (2006) Research paper recommender systems: a random-walk based approach. In: Proceedings of IEEE/WIC/ACM Web Intelligence, pp 778–781
Zurück zum Zitat Kang U, Faloutsos C (2011) Beyond ‘caveman communities’: hubs and spokes for graph compression and mining. In: Proceedings of IEEE International Conference Data Mining, pp 300–309 Kang U, Faloutsos C (2011) Beyond ‘caveman communities’: hubs and spokes for graph compression and mining. In: Proceedings of IEEE International Conference Data Mining, pp 300–309
Zurück zum Zitat Kessler MM (1963) Bibliographic coupling between scientific papers. American Documentation 14:10–25CrossRef Kessler MM (1963) Bibliographic coupling between scientific papers. American Documentation 14:10–25CrossRef
Zurück zum Zitat Kim HN, El-Saddik A (2011) Personalized PageRank vectors for tag recommendations: inside FolkRank. In: Proceedings of ACM Recommender Systems, pp 45–52 Kim HN, El-Saddik A (2011) Personalized PageRank vectors for tag recommendations: inside FolkRank. In: Proceedings of ACM Recommender Systems, pp 45–52
Zurück zum Zitat Küçüktunç O, Kaya K, Saule E, Çatalyürek ÜV (2012a) Fast recommendation on bibliographic networks. In: Proceedings of Advances in Social Networks Analysis and Mining, pp 480–487 Küçüktunç O, Kaya K, Saule E, Çatalyürek ÜV (2012a) Fast recommendation on bibliographic networks. In: Proceedings of Advances in Social Networks Analysis and Mining, pp 480–487
Zurück zum Zitat Küçüktunç O, Saule E, Kaya K, Çatalyürek ÜV (2012b) Direction awareness in citation recommendation. In: Proceedings of International Workshop on Ranking in Databases (DBRank’12) in Conjunction with VLDB’12 Küçüktunç O, Saule E, Kaya K, Çatalyürek ÜV (2012b) Direction awareness in citation recommendation. In: Proceedings of International Workshop on Ranking in Databases (DBRank’12) in Conjunction with VLDB’12
Zurück zum Zitat Lawrence S, Giles CL, Bollacker K (1999) Digital libraries and autonomous citation indexing. Computer 32:67–71CrossRef Lawrence S, Giles CL, Bollacker K (1999) Digital libraries and autonomous citation indexing. Computer 32:67–71CrossRef
Zurück zum Zitat Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Wiley–Teubner, Berlin Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Wiley–Teubner, Berlin
Zurück zum Zitat Li J, Willett P (2009) ArticleRank: a PageRank-based alternative to numbers of citations for analyzing citation networks. Proc Assoc Inform Manag 61(6):605–618 Li J, Willett P (2009) ArticleRank: a PageRank-based alternative to numbers of citations for analyzing citation networks. Proc Assoc Inform Manag 61(6):605–618
Zurück zum Zitat Liben-Nowell D, Kleinberg JM (2007) The link-prediction problem for social networks. J Am Soc Inform Sci 58(7):1019–1031CrossRef Liben-Nowell D, Kleinberg JM (2007) The link-prediction problem for social networks. J Am Soc Inform Sci 58(7):1019–1031CrossRef
Zurück zum Zitat Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web. TR 1999-66, Stanford InfoLab Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web. TR 1999-66, Stanford InfoLab
Zurück zum Zitat Pan JY, Yang HJ, Faloutsos C, Duygulu P (2004) Automatic multimedia cross-modal correlation discovery. In: Proceedings of ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp 653–658 Pan JY, Yang HJ, Faloutsos C, Duygulu P (2004) Automatic multimedia cross-modal correlation discovery. In: Proceedings of ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp 653–658
Zurück zum Zitat Pichel JC, Heras DB, Cabaleiro JC, Rivera FF (2005) Performance optimization of irregular codes based on the combination of reordering and blocking techniques. Parallel Comput 31(8–9):858–876CrossRef Pichel JC, Heras DB, Cabaleiro JC, Rivera FF (2005) Performance optimization of irregular codes based on the combination of reordering and blocking techniques. Parallel Comput 31(8–9):858–876CrossRef
Zurück zum Zitat Pichel JC, Heras DB, Cabaleiro JC, Rivera FF (2009) Increasing data reuse of sparse algebra codes on simultaneous multithreading architectures. Concurr Comput Pract Experience 21(15):1838–1856CrossRef Pichel JC, Heras DB, Cabaleiro JC, Rivera FF (2009) Increasing data reuse of sparse algebra codes on simultaneous multithreading architectures. Concurr Comput Pract Experience 21(15):1838–1856CrossRef
Zurück zum Zitat Pinar A, Heath MT (1999) Improving performance of sparse matrix-vector multiplication. In: Proceedings of ACM/IEEE Supercomputing Pinar A, Heath MT (1999) Improving performance of sparse matrix-vector multiplication. In: Proceedings of ACM/IEEE Supercomputing
Zurück zum Zitat Small H (1973) Co-citation in the scientific literature: a new measure of the relationship between two documents. J Am Soc Inf Sci 24(4):265–269CrossRef Small H (1973) Co-citation in the scientific literature: a new measure of the relationship between two documents. J Am Soc Inf Sci 24(4):265–269CrossRef
Zurück zum Zitat Strohman T, Croft WB, Jensen D (2007) Recommending cictations for academic papers. In: Proceedings of International ACM SIGIR Conference Research and Development in Information Retrieval, pp 705–706 Strohman T, Croft WB, Jensen D (2007) Recommending cictations for academic papers. In: Proceedings of International ACM SIGIR Conference Research and Development in Information Retrieval, pp 705–706
Zurück zum Zitat Temam O, Jalby W (1992) Characterizing the behavior of sparse algorithms on caches. In: Proceedings of ACM/IEEE Supercomputing, pp 578–587 Temam O, Jalby W (1992) Characterizing the behavior of sparse algorithms on caches. In: Proceedings of ACM/IEEE Supercomputing, pp 578–587
Zurück zum Zitat Toledo S (1997) Improving the memory-system performance of sparse-matrix vector multiplication. IBM J Res Dev 41(6):711–726CrossRef Toledo S (1997) Improving the memory-system performance of sparse-matrix vector multiplication. IBM J Res Dev 41(6):711–726CrossRef
Zurück zum Zitat White JB, Sadayappan P (1997) On improving the performance of sparse matrix-vector multiplication. In: Proceedings of International Conference High Performance Computing, pp 66–71 White JB, Sadayappan P (1997) On improving the performance of sparse matrix-vector multiplication. In: Proceedings of International Conference High Performance Computing, pp 66–71
Zurück zum Zitat Yin Z, Gupta M, Weninger T, Han J (2010) A unified framework for link recommendation using random walks. In: Proceedings of Advances in Social Networks Analysis and Mining, pp 152–159 Yin Z, Gupta M, Weninger T, Han J (2010) A unified framework for link recommendation using random walks. In: Proceedings of Advances in Social Networks Analysis and Mining, pp 152–159
Zurück zum Zitat Yzelman AN, Bisseling RH (2009) Cache-oblivious sparse matrix–vector multiplication by using sparse matrix partitioning methods. SIAM J Sci Comput 31:3128–3154MathSciNetCrossRefMATH Yzelman AN, Bisseling RH (2009) Cache-oblivious sparse matrix–vector multiplication by using sparse matrix partitioning methods. SIAM J Sci Comput 31:3128–3154MathSciNetCrossRefMATH
Zurück zum Zitat Yzelman AN, Bisseling RH (2011) Two-dimensional cache-oblivious sparse matrix-vector multiplication. Parallel Comput 37:806–819CrossRef Yzelman AN, Bisseling RH (2011) Two-dimensional cache-oblivious sparse matrix-vector multiplication. Parallel Comput 37:806–819CrossRef
Metadaten
Titel
Fast recommendation on bibliographic networks with sparse-matrix ordering and partitioning
verfasst von
Onur Küçüktunç
Kamer Kaya
Erik Saule
Ümit V. Çatalyürek
Publikationsdatum
01.12.2013
Verlag
Springer Vienna
Erschienen in
Social Network Analysis and Mining / Ausgabe 4/2013
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-013-0106-z

Weitere Artikel der Ausgabe 4/2013

Social Network Analysis and Mining 4/2013 Zur Ausgabe