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

作者：Sagharichian Masoud; Langouri Morteza Alipour; Naderi Hassan^*

来源：World Wide Web-internet and Web Information Systems, 2017, 20(2): 399-416.

DOI：10.1007/s11280-016-0394-0

• Diameter
• Incremental graphs
• Dynamic graphs
• Graph mining

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.

• 出版日期2017-3