Article number 9
Published in RGT on November 24, 2020

Method of graph mining based on the topological anomaly matrix and its application for discovering the structural peculiarities of complex networks

Keywords:
topological anomaly matrix, complex network, graph topology, closeness centrality, betweenness centrality, power grid

Abstract:

The article introduces the mathematical concept of the topological anomaly matrix providing the foundation for the qualitative assessment of the topological organization underlying the large-scale complex networks. The basic idea of the proposed concept consists in translating the distributions of the individual vertex-level characteristics (such as the degree, closeness, and betweenness centrality) into the integrative properties of the overall graph. The article analyzes the lower bounds imposed on the items of the topological anomaly matrix and obtains the new fundamental results enriching the graph theory. With a view to improving the interpretability of these results, the article introduces and proves the theorem regarding the smoothness of the closeness centrality distribution over the graph’s vertices. By performing the series of experiments, the article illustrates the application of the proposed matrix for evaluating the topology of the real-world power grid network and its post-attack damage.

References:

1. M. Khan, X. Wu, X. Xu, and W. Dou, “Big Data challenges and opportunities in the hype of industry 4.0,” in Communications (ICC), 2017 IEEE International Conference on, pp. 1 – 6, 2017.

View in Google Scholar

2. Y. Lu, “Industry 4.0: A survey on technologies, applications and open research issues,” Journal of Industrial Information Integration, vol. 6, pp. 1 – 10, 2017.

View in Google Scholar

3. A. Potebnia, “Innovative metrics for assessing the catastrophic collapse of the complex networks under the greedy attacks on their most important vertices and edges,” in Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), 14th International Conference on, pp. 564 – 569, 2018.

View in Google Scholar

4. A. Potebnia, “Innovative concept of the strict line hypergraph as the basis for specifying the duality relation between the vertex separators and cuts,” in Advances in Intelligent Systems and Computing II. CSIT 2017. Advances in Intelligent Systems and Computing, vol. 689, Springer International Publishing, pp. 386 – 403, 2018.

View in Google Scholar

5. Y. Huang, G. Wang, and Y. Tang, “Bottleneck attack strategies on complex communication networks,” in Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence. ICIC 2010. Lecture Notes in Computer Science, vol. 6216. Springer-Verlag Berlin Heidelberg, pp. 418 – 425, 2010.

View in Google Scholar

6. A. Potebnia, “New method for estimating the tree-likeness of graphs and its application for tracing the robustness of complex networks,” in Computing, Communication and Networking Technologies (ICCCNT), 9th International Conference on, 2018.

View in Google Scholar

7. Y.-K. Wu, S.M. Chang, and Y.-L. Hu, “Literature review of power system blackouts,” Energy Procedia, vol. 141, pp. 428 – 431, 2017.

View in Google Scholar

8. S. Soltan, D. Mazauric, and G. Zussman, “Analysis of failures in power grids,” IEEE Transactions on Control of Network Systems, vol. 4(2), pp. 288 – 300, 2017.

View in Google Scholar

9. L. Liu, Y. Yin, Z. Zhang, and Y.K. Malaiya, “Redundant design in interdependent networks,” PLoS ONE, vol. 11(10):e0164777, 2016.

View in Google Scholar

10. J.A. Miller, L. Ramaswamy, K.J. Kochut, and A. Fard, “Research directions for Big Data graph analytics,” in Big Data (BigData Congress), 2015 IEEE International Congress on, pp. 785 – 794, 2015.

View in Google Scholar

11. M.U. Nisar, A. Fard, and J.A. Miller, “Techniques for graph analytics on Big Data”, in Big Data (BigData Congress), 2013 IEEE International Congress on, pp. 255 – 262, 2013.

View in Google Scholar

12. B. Kantarci and V. Labatut, “Classification of complex networks based on topological properties,” in Cloud and Green Computing (CGC), 2013 Third International Conference on, pp. 297 – 304, 2013.

View in Google Scholar

13. K. Das, S. Samanta, and M. Pal, “Study on centrality measures in social networks: a survey,” Social Network Analysis and Mining, vol. 8:13, 2018.

View in Google Scholar

14. N. Matas, S. Martincic-Ipsic, and A. Mestrovic, “Comparing network centrality measures as tools for identifying key concepts in complex networks: A case of Wikipedia,” Journal of Digital Information Management, vol. 15(4), pp. 203 – 213, 2017.

View in Google Scholar

15. S. Fortunato and C. Castellano, “Community structure in graphs,” in Computational Complexity. Springer New York, pp. 490 – 512, 2012.

View in Google Scholar

16. G. Lin, Z. Di, and Y. Fan, “Cascading failures in complex networks with community structure,” International Journal of Modern Physics C, vol. 25(5): 1440005, 2014.

View in Google Scholar

17. US power grid network dataset. KONECT: The Koblenz Network Collection. Available online: http://konect.uni-koblenz.de/networks/opsahl-powergrid. Accessed: April 2018.

View in Google Scholar

Full Text:

2020

Abstract viewed:
15

PDF downloaded:
2
How to Cite:
IEEE Citation Style
▾
  • IEEE Citation Style
  • ACM Citation Style
  • APA Citation Style
  • Harvard Citation Style
  • MLA Citation Style
  • Turabian Citation Style
  • Chicago Citation Style
A. Potebnia, “Method of graph mining based on the topological anomaly matrix and its application for discovering the structural peculiarities of complex networks,” International Journal of Advanced Computer Science and Applications, vol. 9, no. 9, pp. 42 – 48, 2018. DOI: 10.​14569/​IJACSA.​2018.​​090906. Open-access version available at https://purl.org/artempotebnia/9
Section:
Original Scientific Articles in Graph Theory
Universal Resource Name:
https:/
/
purl.
org/
artempotebnia/
9
Reading Tools:
Method of graph mining based on the topological anomaly matrix and its application for discovering the structural peculiarities of complex networks

Authored by: Artem Potebnia
ORCID: https://orcid.org/0000-0002-8162-5613

Keywords: topological anomaly matrix, complex network, graph topology, closeness centrality, betweenness centrality, power grid

Abstract: The article introduces the mathematical concept of the topological anomaly matrix providing the foundation for the qualitative assessment of the topological organization underlying the large-scale complex networks. The basic idea of the proposed concept consists in translating the distributions of the individual vertex-level characteristics (such as the degree, closeness, and betweenness centrality) into the integrative properties of the overall graph. The article analyzes the lower bounds imposed on the items of the topological anomaly matrix and obtains the new fundamental results enriching the graph theory. With a view to improving the interpretability of these results, the article introduces and proves the theorem regarding the smoothness of the closeness centrality distribution over the graph’s vertices. By performing the series of experiments, the article illustrates the application of the proposed matrix for evaluating the topology of the real-world power grid network and its post-attack damage.