New method for estimating the tree-likeness of graphs and its application for tracing the robustness of complex networks
Abstract:
This article presents the original metric of the minimum cyclic reachability distribution providing the foundation for assessing the topological tree-likeness of the large-scale sparse graphs. The conceptual sense enclosed in the proposed metric lies in interpreting the similarity of the analyzed graph to a tree based on the position of each its vertex in the structure of the graph's paths. With a view to demonstrate the theoretical value of the introduced metric, the article deals with its applying for discovering the dependence of the topological tree-likeness of the random graphs on the parameters of their generation. Finally, the article illustrates the usage of the designed metric for estimating the robustness of the complex networks and pursues the experimental analysis of the graph model constructed for the real-world power transmission network.
References:
S. Iyer, T. Killingback, B. Sundaram and Z. Wang, "Attack robustness and centrality of complex networks", PLoS ONE, vol. 8, no. 4, 2013.
View in Google ScholarM. Samer and H. Veith, "Encoding treewidth into SAT" in Theory and Applications of Satisfiability Testing. SAT 2009, Springer-Verlag, vol. 5584, pp. 45-50, 2009.
View in Google ScholarJ. Berg and M. Jarvisalo, "SAT-based approaches to treewidth computation: an evaluation", Tools with Artificial Intelligence IEEE 26th International Conference on, pp. 328-335, 2014.
View in Google ScholarL. Tian, A. Bashan, D.-N. Shi and Y.-Y. Liu, "Articulation points in complex networks", Nature Communications, vol. 8, 2017.
View in Google ScholarA. Potebnia, "Algebra for transforming the structure of the search spaces associated with the combinatorial optimization problems", Journal of Theoretical and Applied Information Technology, vol. 95, no. 15, pp. 3644-3651, 2017.
View in Google ScholarM.N. Ellingham and D.K. Menser, "Girth minimum degree and circumference", Journal of Graph Theory, vol. 34, no. 3, pp. 221-233, 2000.
View in Google ScholarK. Panagiotou, R. Spohel, A. Steger and H. Thomas, "Explosive percolation in Erdos-Renyi-like random graph processes", Electronic Notes in Discrete Mathematics, vol. 38, pp. 699-704, 2011.
View in Google ScholarA. Potebnia, "Innovative concept of the strict line hypergraph as the basis for specifying the duality relation between the vertex separators and cuts", Advances in Intelligent Systems and Computing II. CSIT 2017. Advances in Intelligent Systems and Computing, vol. 689, pp. 386-403, 2018.
View in Google ScholarUS power grid network dataset. KONECT: The Koblenz Network Collection, [online] Available: http://konect.uni-koblenz.de/networks/opsahl-powergrid.
View in Google Scholar
