JUCS - Journal of Universal Computer Science 22(3): 302-318, doi: 10.3217/jucs-022-03-0302
Calculating Exact Diameter Metric of Large Static Graphs
Masoud Sagharichian‡, Morteza Alipour Langouri‡, Hassan Naderi‡‡ Iran University of Science and Technology, Tehran, Iran
Corresponding author: Masoud Sagharichian ( sagharichian@iust.ac.ir ) © Masoud Sagharichian, Morteza Langouri, Hassan Naderi. This article is freely available under the J.UCS Open Content License. Citation:
Sagharichian M, Langouri MA, Naderi H (2016) Calculating Exact Diameter Metric of Large Static Graphs. JUCS - Journal of Universal Computer Science 22(3): 302-318. https://doi.org/10.3217/jucs-022-03-0302 |  |
Abstract
The variety of applications requiring graph analysis 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. So, detecting diameter of large graphs is very important. We propose an algorithm to calculate the diameter of such graphs. The main goal of this algorithm is to reduce the number of breadth-first searches required to determine the diameter of the graph by finding a better upper bound for the eccentricity of vertices. Based on experimental results, our proposed algorithm can quickly detect the exact diameter of the large-scale real world graphs with a few number of breadth-first searches.
Keywords
diameter, static graphs, graph mining, social networks