Calculating Exact Diameter Metric of Large Static Graphs

Masoud Sagharichian (Iran University of Science and Technology, Iran)

Morteza Alipour Langouri (Iran University of Science and Technology, Iran)

Hassan Naderi (Iran University of Science and Technology, Iran)

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, graph mining, social networks, static graphs

Categories: F.2, J.1, J.4, K.4.2