A subset selection based approach to finding important structure of complex networks

Abstract

Most of the real world networks such as the internet network, collaboration networks, brain networks, citation networks, powerline and airline networks are very large and to study their structure, and dynamics one often requires working with large connectivity (adjacency) matrices. However, it is almost always true that a few or sometimes most of the nodes and their connections are not very crucial for network functioning or that the network is robust to a failure of certain nodes and their connections to the rest of the network. In the present work, we aim to extract the size reduced representation of complex networks such that new representation has the most relevant network nodes and connections and retains its spectral properties. To achieve this, we use the Subset Selection (SS) procedure. The SS method, in general, is used to retrieve maximum information from a matrix in terms of its most informative columns. The retrieved matrix, typically known as subset has columns of an original matrix that have the least linear dependency. We present the application of SS procedure to many adjacency matrices of real-world networks and model network types to extract their subset. The subset owing to its small size can play a crucial role in analyzing spectral properties of large complex networks where space and time complexity of analyzing full adjacency matrices are too expensive. The adjacency matrix constructed from the obtained subset has a smaller size and represents the most important network structure. We observed that the subset network which is almost half the size of the original network has better information flow efficiency than the original network.