Graph Toughness Computation In Distributed Environment

As the rapid development of social network applications, research on large scale graph data processing is becoming more and more essential. Large scale graph processing has its own features, including weak locality, frequent I/O operations, hard to parallize, very large scale intermediate results, etc. Toughness is a graph factor introduced by Chavtal in 1973, denoting the structural stability of a graph. Compared with graph vertex connectivity and graph edge connectivity, graph toughness can provide more information on graph structural stability. For any fixed positive rational k, it is co NP-complete to decide whether a graph is k-tough.Despite its computational hardness, graph toughness factor plays an important role in traffic network analysis and social network analysis. We investigate into distributed approximate graph toughness computing and we design a toughness lower bound algorithm: Lower Lap, using graph Laplacian eigenvalues. We design two approximate algorithms: BFS-T, based on breadth first traversal and Page Rank-T, based on short random walk Page Rank.Using synthetic graph data and realworld road network data, we implement above algorithms using Apache Spark distributed computing platform and experimentally evaluated their effectiveness. Additionally, we design and implement a resource trace and optimizing system. By adjust graph partitioning, initial vertex selecting and bottleneck analysis, we further imporove the computation efficiency.