One Node at a Time: Node-Level Network Classification

Abstract

Network classification aims to group networks (or graphs) into distinct categories based on their structure. We study the connection between classification of a network and of its constituent nodes, and whether nodes from networks in different groups are distinguishable based on structural node characteristics such as centrality and clustering coefficient. We demonstrate, using various network datasets and random network models, that a classifier can be trained to accurately predict the network category of a given node (without seeing the whole network), implying that complex networks display distinct structural patterns even at the node level. Finally, we discuss two applications of node-level network classification: (i) whole-network classification from small samples of nodes, and (ii) network bootstrapping.

arXiv comment8 pages, 5 figures

References in corpus (15)

• Emergence of scaling in random networks
• Modularity and community structure in networks
• DeepWalk: Online Learning of Social Representations
• From Louvain to Leiden: guaranteeing well-connected communities
• Finding community structure in networks using the eigenvectors of matrices
• LINE: Large-scale Information Network Embedding
• Growing Scale-Free Networks with Tunable Clustering
• Biological network comparison using graphlet degree distribution
• Social Structure of Facebook Networks
• Spectral redemption: clustering sparse networks
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• A Survey on Graph Kernels
• NetSimile: A Scalable Approach to Size-Independent Network Similarity
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• Revealing effective classifiers through network comparison