Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInterplay between $k$-core and community structure in complex networks
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The organisation of a network in a maximal set of nodes having at least $k$ neighbours within the set, known as $k$-core decomposition, has been used for studying various phenomena. It has been shown that nodes in the innermost $k$-shells play a crucial role in contagion processes, emergence of consensus, and resilience of the system. It is known that the $k$-core decomposition of many empirical networks cannot be explained by the degree of each node alone, or equivalently, random graph models that preserve the degree of each node (i.e., configuration model). Here we study the $k$-core decomposition of some empirical networks as well as that of some randomised counterparts, and examine the extent to which the $k$-shell structure of the networks can be accounted for by the community structure. We find that preserving the community structure in the randomisation process is crucial for generating networks whose $k$-core decomposition is close to the empirical one. We also highlight the existence, in some networks, of a concentration of the nodes in the innermost $k$-shells into a small number of communities.
rate research
Read More
Core-periphery structure and community structure are two typical meso-scale structures in complex networks. Though the community detection has been extensively investigated from different perspectives, the definition and the detection of core-periphery structure have not received much attention. Furthermore, the detection problems of the core-periphery and community structure were separately investigated. In this paper, we develop a unified framework to simultaneously detect core-periphery structure and community structure in complex networks. Moreover, there are several extra advantages of our algorithm: our method can detect not only single but also multiple pairs of core-periphery structures; the overlapping nodes belonging to different communities can be identified; different scales of core-periphery structures can be detected by adjusting the size of core. The good performance of the method has been validated on synthetic and real complex networks. So we provide a basic framework to detect the two typical meso-scale structures: core-periphery structure and community structure.
Multiplex networks are convenient mathematical representations for many real-world -- biological, social, and technological -- systems of interacting elements, where pairwise interactions among elements have different flavors. Previous studies pointed out that real-world multiplex networks display significant inter-layer correlations -- degree-degree correlation, edge overlap, node similarities -- able to make them robust against random and targeted failures of their individual components. Here, we show that inter-layer correlations are important also in the characterization of their $mathbf{k}$-core structure, namely the organization in shells of nodes with increasingly high degree. Understanding $k$-core structures is important in the study of spreading processes taking place on networks, as for example in the identification of influential spreaders and the emergence of localization phenomena. We find that, if the degree distribution of the network is heterogeneous, then a strong $mathbf{k}$-core structure is well predicted by significantly positive degree-degree correlations. However, if the network degree distribution is homogeneous, then strong $mathbf{k}$-core structure is due to positive correlations at the level of node similarities. We reach our conclusions by analyzing different real-world multiplex networks, introducing novel techniques for controlling inter-layer correlations of networks without changing their structure, and taking advantage of synthetic network models with tunable levels of inter-layer correlations.
Community detection is expensive, and the cost generally depends at least linearly on the number of vertices in the graph. We propose working with a reduced graph that has many fewer nodes but nonetheless captures key community structure. The K-core of a graph is the largest subgraph within which each node has at least K connections. We propose a framework that accelerates community detection by applying an expensive algorithm (modularity optimization, the Louvain method, spectral clustering, etc.) to the K-core and then using an inexpensive heuristic (such as local modularity maximization) to infer community labels for the remaining nodes. Our experiments demonstrate that the proposed framework can reduce the running time by more than 80% while preserving the quality of the solutions. Recent theoretical investigations provide support for using the K-core as a reduced representation.
We present a new layout algorithm for complex networks that combines a multi-scale approach for community detection with a standard force-directed design. Since community detection is computationally cheap, we can exploit the multi-scale approach to generate network configurations with close-to-minimal energy very fast. As a further asset, we can use the knowledge of the community structure to facilitate the interpretation of large networks, for example the network defined by protein-protein interactions.
Community structure is one of the most relevant features encountered in numerous real-world applications of networked systems. Despite the tremendous effort of scientists working on this subject over the past few decades to characterize, model, and analyze communities, more investigations are needed to better understand the impact of community structure and its dynamics on networked systems. Here, we first focus on generative models of communities in complex networks and their role in developing strong foundation for community detection algorithms. We discuss modularity and the use of modularity maximization as the basis for community detection. Then, we overview the Stochastic Block Model, its different variants, and inference of community structures from such models. Next, we focus on time evolving networks, where existing nodes and links can disappear and/or new nodes and links may be introduced. The extraction of communities under such circumstances poses an interesting and non-trivial problem that has gained considerable interest over the last decade. We briefly discuss considerable advances made in this field recently. Finally, we focus on immunization strategies essential for targeting the influential spreaders of epidemics in modular networks. Their main goal is to select and immunize a small proportion of individuals from the whole network to control the diffusion process. Various strategies have emerged over the years suggesting different ways to immunize nodes in networks with overlapping and non-overlapping community structure. We first discuss stochastic strategies that require little or no information about the network topology at the expense of their performance. Then, we introduce deterministic strategies that have proven to be very efficient in controlling the epidemic outbreaks, but require complete knowledge of the network.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
