Community-based method for extracting backbones

Networks are an adequate representation for modeling and analyzing a great variety of complex systems. However, understanding networks with millions of nodes and billions of connections can be pretty challenging due to memory and time constraints. Therefore, selecting the relevant nodes and edges of these large-scale networks while preserving their core information is a major issue. In most cases, the so-called backbone extraction methods are based either on coarse-graining or filtering approaches. Coarse-graining techniques reduce the network size by gathering similar nodes into super-nodes, while filter-based methods eliminate nodes or edges according to a statistical property. In this work, a filter-based method is proposed and investigated. It uses the overlapping community structure to build the backbone in weighted networks. While most filtering techniques rely on link features to extract the backbone, the proposed method exploits both nodes and links. It takes advantage of the network communities through their main features (overlapping nodes, hubs, and bridging connections) to select influential edges and nodes while preserving the ability of the information dissemination of the original network. The so-called “Modular filtering backbone” combines two components. The first one is the network connecting the overlapping nodes and the top connected nodes (also called the hubs). One discards the edges with the lowest weights as long as connected components are maintained. The second component uses the network of the inter-community links with the nodes at their extremities. The disparity filter algorithm allows preserving only its most crucial connections. An extensive investigation is performed on a set of real-world weighted networks of various sizes and a wide range of origin. Results show the advantage of the proposed method over alternative filtering-based methods used for comparative purposes. Furthermore, this sheds new light on the most relevant parts of empirical networks hidden by their complexity.