nach oben

World Wide Web

Erschienen in:

27.05.2016

A fast method to exactly calculate the diameter of incremental disconnected graphs

verfasst von: Masoud Sagharichian, Morteza Alipour Langouri, Hassan Naderi

Erschienen in: World Wide Web | Ausgabe 2/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The breadth of problems requiring graph analytics is growing rapidly. Diameter is one of the most important metrics of a graph. The diameter is important in both designing algorithms for graphs and understanding the nature and evolution of graphs. Besides, the real world graphs are always changing. So detecting diameter in both static and dynamic graphs is very important. We first present an algorithm to calculate the diameter of the static graphs. The main goal of this algorithm is to reduce the number of breadth-first searches required to determine diameter of the graph. In addition, another algorithm is presented for calculating the diameter of incremental graphs. This algorithm uses the proposed static algorithm in its body. Based on experimental results, our proposed algorithm can detect diameter of both static and incremental graphs faster than existing approaches. To the best of our knowledge, the second algorithm is the first one that is able to efficiently determine the diameter of disconnected graphs that will be connected over time by adding new vertices.

Vorheriger Artikel Multiple k nearest neighbor search

Nächster Artikel Discerning individual interests and shared interests for social user profiling

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

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Akiba, T., Iwata, Y., Kawata, Y.: An exact algorithm for diameters of large real directed graphs. In: Experimental Algorithms, pp. 56–67. Springer (2015)

Bawa, M., Cooper, B.F., Crespo, A., Daswani, N., Ganesan, P., Garcia-Molina, H., Kamvar, S., Marti, S., Schlosser, M., Sun, Q.: Peer-to-peer research at Stanford. ACM SIGMOD Rec. 32(3), 23–28 (2003)CrossRef

Chechik, S., Larkin, D.H., Roditty, L., Schoenebeck, G., Tarjan, R.E., Williams, V.: Better approximation algorithms for the graph diameter. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1041–1052. SIAM (2014)

Chung, F., Lu, L.: The diameter of sparse random graphs. Adv. Appl. Math. 26(4), 257–279 (2001)MathSciNetCrossRefMATH

Crescenzi, P., Grossi, R., Habib, M., Lanzi, L., Marino, A.: On computing the diameter of real-world undirected graphs. Theor. Comput. Sci. 514, 84–95 (2013)MathSciNetCrossRefMATH

Crescenzi, P., Grossi, R., Imbrenda, C., Lanzi, L., Marino, A.: Finding the diameter in real-world graphs. In: Algorithms--ESA 2010, pp. 302–313. Springer (2010)

Crescenzi, P., Grossi, R., Lanzi, L., Marino, A.: On computing the diameter of real-world directed (weighted) graphs. In: Experimental Algorithms, pp. 99–110. Springer (2012)

Fujiwara, Y., Onizuka, M., Kitsuregawa, M.: Real-time diameter monitoring for time-evolving graphs. In: Database Systems for Advanced Applications, pp. 311–325. Springer (2011)

Jure, L., Andrej, K.: SNAP datasets: Stanford large network dataset collection. [Online]. Available: http://snap.stanford.edu/data (2014)

10.

Kumar, A., Merugu, S., Xu, J.J., Zegura, E.W., Yu, X.: Ulysses: a robust, low-diameter, low-latency peer-to-peer network. Eur. Trans. Telecommun. 15(6), 571–587 (2004)CrossRef

11.

Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 135–146. ACM (2010)

12.

Masoud, S., Hassan, N., Mostafa, H.: ExPregel: a new computational model for large-scale graph processing. Concurr. Comput. 27(17), 4954–4969 (2015)CrossRef

13.

Newman, M.E.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)MathSciNetCrossRefMATH

14.

Reka, A., Hawoong, J., Albert-Laszlo, B.: Internet: Diameter of the world-wide web. Nature 401(6749), 130–131 (1999)CrossRef

15.

Roditty, L., Vassilevska Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 515–524. ACM (2013)

16.

Shudong, J., Azer, B.: Small-world characteristics of internet topologies and implications on multicast scaling. Comput. Netw. 50(5), 648–666 (2006)CrossRefMATH

17.

Takes, F.W., Kosters, W.A.: Determining the diameter of small world networks. In: Proceedings of the 20th ACM international conference on Information and knowledge management, pp. 1191–1196. ACM (2011)

18.

Walshaw, C.: The university of greenwich gaph partitioning archive. [Online]. Available: http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/ ( 2000). Accessed 2015

19.

Wasserman, S.: Social network analysis Methods and applications. Cambridge University Press (1994)

20.

Yan, D., Cheng, J., Lu, Y., Ng, W.: Blogel: A block-centric framework for distributed computation on real-world graphs. Proc. VLDB Endow. 7(14), 1981–1992 (2014)CrossRef

21.

Yuster, R.: Computing the diameter polynomially faster than APSP. arXiv preprint arXiv:1011.6181 (2010)

22.

Zwick, U.: Exact and approximate distances in graphs—a survey. In: Algorithms—ESA 2001, pp. 33–48. Springer (2001)

Titel: A fast method to exactly calculate the diameter of incremental disconnected graphs
verfasst von: Masoud Sagharichian
Morteza Alipour Langouri
Hassan Naderi
Publikationsdatum: 27.05.2016
Verlag: Springer US
Erschienen in: World Wide Web / Ausgabe 2/2017
Print ISSN: 1386-145X
Elektronische ISSN: 1573-1413
DOI: https://doi.org/10.1007/s11280-016-0394-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2017

Adaptive task scheduling strategy in cloud: when energy consumption meets performance guarantee

Subscription-based data aggregation techniques for top-k monitoring queries

Multiple k nearest neighbor search

Trip planning queries with location privacy in spatial databases

Twitter summarization with social-temporal context

Categorical top-k spatial influence query

Premium Partner