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.

8 pages, 5 figures

References in corpus (6)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• LINE: Large-scale Information Network Embedding
• Biological network comparison using graphlet degree distribution
• NetSimile: A Scalable Approach to Size-Independent Network Similarity
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism