Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCommunity Structure in Graphs
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Graph vertices are often organized into groups that seem to live fairly independently of the rest of the graph, with which they share but a few edges, whereas the relationships between group members are stronger, as shown by the large number of mutual connections. Such groups of vertices, or communities, can be considered as independent compartments of a graph. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. The task is very hard, though, both conceptually, due to the ambiguity in the definition of community and in the discrimination of different partitions and practically, because algorithms must find ``good partitions among an exponentially large number of them. Other complications are represented by the possible occurrence of hierarchies, i.e. communities which are nested inside larger communities, and by the existence of overlaps between communities, due to the presence of nodes belonging to more groups. All these aspects are dealt with in some detail and many methods are described, from traditional approaches used in computer science and sociology to recent techniques developed mostly within statistical physics.
rate research
Read More
Many networks in nature, society and technology are characterized by a mesoscopic level of organization, with groups of nodes forming tightly connected units, called communities or modules, that are only weakly linked to each other. Uncovering this community structure is one of the most important problems in the field of complex networks. Networks often show a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities. Here we present the first algorithm that finds both overlapping communities and the hierarchical structure. The method is based on the local optimization of a fitness function. Community structure is revealed by peaks in the fitness histogram. The resolution can be tuned by a parameter enabling to investigate different hierarchical levels of organization. Tests on real and artificial networks give excellent results.
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.
Social structures emerge as a result of individuals managing a variety of different of social relationships. Societies can be represented as highly structured dynamic multiplex networks. Here we study the dynamical origins of the specific community structures of a large-scale social multiplex network of a human society that interacts in a virtual world of a massive multiplayer online game. There we find substantial differences in the community structures of different social actions, represented by the various network layers in the multiplex. Community size distributions are either similar to a power-law or appear to be centered around a size of 50 individuals. To understand these observations we propose a voter model that is built around the principle of triadic closure. It explicitly models the co-evolution of node- and link-dynamics across different layers of the multiplex. Depending on link- and node fluctuation rates, the model exhibits an anomalous shattered fragmentation transition, where one layer fragments from one large component into many small components. The observed community size distributions are in good agreement with the predicted fragmentation in the model. We show that the empirical pairwise similarities of network layers, in terms of link overlap and degree correlations, practically coincide with the model. This suggests that several detailed features of the fragmentation in societies can be traced back to the triadic closure processes.
Spectral analysis has been successfully applied at the detection of community structure of networks, respectively being based on the adjacency matrix, the standard Laplacian matrix, the normalized Laplacian matrix, the modularity matrix, the correlation matrix and several other variants of these matrices. However, the comparison between these spectral methods is less reported. More importantly, it is still unclear which matrix is more appropriate for the detection of community structure. This paper answers the question through evaluating the effectiveness of these five matrices against the benchmark networks with heterogeneous distributions of node degree and community size. Test results demonstrate that the normalized Laplacian matrix and the correlation matrix significantly outperform the other three matrices at identifying the community structure of networks. This indicates that it is crucial to take into account the heterogeneous distribution of node degree when using spectral analysis for the detection of community structure. In addition, to our surprise, the modularity matrix exhibits very similar performance to the adjacency matrix, which indicates that the modularity matrix does not gain desired benefits from using the configuration model as reference network with the consideration of the node degree heterogeneity.
Most previous studies of epidemic dynamics on complex networks suppose that the disease will eventually stabilize at either a disease-free state or an endemic one. In reality, however, some epidemics always exhibit sporadic and recurrent behaviour in one region because of the invasion from an endemic population elsewhere. In this paper we address this issue and study a susceptible-infected-susceptible epidemiological model on a network consisting of two communities, where the disease is endemic in one community but alternates between outbreaks and extinctions in the other. We provide a detailed characterization of the temporal dynamics of epidemic patterns in the latter community. In particular, we investigate the time duration of both outbreak and extinction, and the time interval between two consecutive inter-community infections, as well as their frequency distributions. Based on the mean-field theory, we theoretically analyze these three timescales and their dependence on the average node degree of each community, the transmission parameters, and the number of intercommunity links, which are in good agreement with simulations, except when the probability of overlaps between successive outbreaks is too large. These findings aid us in better understanding the bursty nature of disease spreading in a local community, and thereby suggesting effective time-dependent control strategies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
