Machine Learning in Network Centrality Measures: Tutorial and Outlook

Abstract

Complex networks are ubiquitous to several Computer Science domains. Centrality measures are an important analysis mechanism to uncover vital elements of complex networks. However, these metrics have high computational costs and requirements that hinder their applications in large real-world networks. In this tutorial, we explain how the use of neural network learning algorithms can render the application of the metrics in complex networks of arbitrary size. Moreover, the tutorial describes how to identify the best configuration for neural network training and learning such for tasks, besides presenting an easy way to generate and acquire training data. We do so by means of a general methodology, using complex network models adaptable to any application. We show that a regression model generated by the neural network successfully approximates the metric values and therefore are a robust, effective alternative in real-world applications. The methodology and proposed machine learning model use only a fraction of time with respect to other approximation algorithms, which is crucial in complex network applications.

arXiv comment7 tables, 9 figures, version accepted at ACM Computing Surveys. https://doi.org/10.1145/3237192

References in corpus (12)

• Emergence of scaling in random networks
• Finding and evaluating community structure in networks
• Characterization of complex networks: A survey of measurements
• Why social networks are different from other types of networks
• Subgraph Centrality in Complex Networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Robust network community detection using balanced propagation
• A Scalable Generative Graph Model with Community Structure
• Communicability Betweenness in Complex Networks
• Computing Classic Closeness Centrality, at Scale
• Functional centrality in graphs
• Random Walks on Complex Networks

Cited by in corpus (6)

• Supervised Feature Selection Techniques in Network Intrusion Detection: a Critical Review
• Experimental Review of Neural-based approaches for Network Intrusion Management
• Approximating Network Centrality Measures Using Node Embedding and Machine Learning
• Network connectivity under a probabilistic node failure model
• Multitask Learning on Graph Neural Networks: Learning Multiple Graph Centrality Measures with a Unified Network
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks