"Efficient Optimization of Diameter and Average Shortest Path Length of a Graph using Path Count Index"
Invited keynote talk at Graph Golf Workshop at The Fourth International Symposium on Computing and Networking (CANDAR'16)
In this talk, we present an efficient method to find an undirected and unweighted graph having a smaller diameter and a shorter average shortest path length (ASPL) with given order and degree. For this problem, local search is one of the most common techniques to find a better solution. However, due to the high computation cost of the objective functions (diameter and ASPL of a graph), the naive local search is not practical for large graphs. Our proposed technique reduces the computation cost drastically by using alternative objective functions that estimate the real objective functions. The key for the higher performance is that what we actually need for the local search is not the diameter and ASPL of the graph, but the changes of them due to a small modification applied for the graph; the changes can be calculated using only the local information around the modified edges without involving the whole graph. To calculate the changes without fully recomputing the node-to-node distances, a new data structure called Path Count Index is introduced. Our technique accelerated the local search significantly (by order of 10^5 in maximum). Although the Path Count Index consumed additional memory space, it was possible to execute the local search for graphs with up to 10,000 nodes on a commodity PC with 4 GB of system memory.