Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Robustness of Spatial Preferential Attachment Networks Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank

Authors : Fan Chung, Olivia Simpson

Published in: Algorithms and Models for the Web Graph

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the problem of computing local clusters in large graphs distributed across nodes in a network using two different models of distributed computation. We give a distributed algorithm that computes a local cluster in time that depends only logarithmically on the size of the graph in the CONGEST model. In particular, when the conductance of the optimal local cluster is known, the algorithm runs in time entirely independent of the size of the graph and depends only on error bounds for approximation. We also show that the local cluster problem can be computed in the k-machine distributed model in sublinear time. The speedup of our local cluster algorithms is mainly due to the use of our distributed algorithm for heat kernel pagerank.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Bidirectional PageRank Estimation: From Average-Case to Worst-Case
next chapter Strong Localization in Personalized PageRank Vectors
Literature
1.
Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: FOCS, pp. 475–486. IEEE (2006)
2.
Andersen, R., Peres, Y.: Finding sparse cuts locally using evolving sets. In: STOC, pp. 235–244. ACM (2009)
3.
Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. JACM 56(2), 1–37 (2009). Article no. 5CrossRefMathSciNet
4.
Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst. 30(1), 107–117 (1998)CrossRef
5.
Chung, F.: Spectral Graph Theory. American Mathematical Society, Providence (1997)MATH
6.
Chung, F., Simpson, O.: Computing heat kernel pagerank and a local clustering algorithm. In: Jan, K., Miller, M., Froncek, D. (eds.) IWOCA 2014. LNCS, vol. 8986, pp. 110–121. Springer, Heidelberg (2015) CrossRef
7.
8.
Chung, F., Simpson, O.: Distributed algorithms for finding local clusters using heat kernel pagerank. arXiv preprint arXiv:​1507.​08967 (2015)
9.
Das Sarma, A., Molla, A.R., Pandurangan, G.: Distributed computation of sparse cuts via random walks. In: ICDCN, pp. 6:1–6:10 (2015)
10.
Das Sarma, A., Molla, A.R., Pandurangan, G., Upfal, E.: Fast distributed pagerank computation. In: Frey, D., Raynal, M., Sarkar, S., Shyamasundar, R.K., Sinha, P. (eds.) ICDCN 2013. LNCS, vol. 7730, pp. 11–26. Springer, Heidelberg (2013) CrossRef
11.
Das Sarma, A., Nanongkai, D., Pandurangan, G., Tetali, P.: Distributed random walks. JACM 60(1), 201–210 (2013). Article no. 2
12.
Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. In: OSDI (2004)
13.
Gharan, S.O., Trevisan, L.: Approximating the expansion profile and almost optimal local graph clustering. In: FOCS, pp. 187–196. IEEE (2012)
14.
Klauck, H., Nanongkai, D., Pandurangan, G., Robinson, P.: Distributed computation of large-scale graph problems. In: SODA, pp. 391–410. SIAM (2015)
15.
Kloster, K., Gleich, D.F.: Heat kernel based community detection. In: ACM SIGKDD, pp. 1386–1395. ACM (2014)
16.
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks. In: WWW, pp. 695–704. ACM (2008)
17.
Liao, C.S., Lu, K., Baym, M., Singh, R., Berger, B.: Isorankn: spectral methods for global alignment of multiple protein networks. Bioinformatics 25(12), i253–i258 (2009)CrossRef
18.
Lovász, L., Simonovits, M.: The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. In: FOCS, pp. 346–354. IEEE (1990)
19.
Lovász, L., Simonovits, M.: Random walks in a convex body and an improved volume algorithm. Random Struct. Algorithms 4(4), 359–412 (1993)CrossRefMATH
20.
Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., Hellerstein, J.M.: Graphlab: a new framework for parallel machine learning. In: UAI, pp. 340–349 (2010)
21.
Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: SIGMOD International Conference on Management of data, pp. 135–146. ACM (2010)
22.
Orecchia, L., Sachdeva, S., Vishnoi, N.K.: Approximating the exponential, the lanczos method and an \(\tilde{O}\)(m)-time spectral algorithm for balanced separator. In: STOC, pp. 1141–1160. ACM (2012)
23.
Pandurangan, G., Khan, M.: Theory of communication networks. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC, Boca Raton (2010)
24.
Peleg, D.: Distributed computing. In: SIAM Monographs on Discrete Mathematics and Applications 5 (2000)
25.
Spielman, D.A., Teng, S.H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: STOC, pp. 81–90. ACM (2004)
Metadata
Title
Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank
Authors
Fan Chung
Olivia Simpson
Copyright Year
2015
Book
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-26783-8

Electronic ISBN: 978-3-319-26784-5

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26784-5_14

Premium Partner

    Image Credits