اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEvaluating Local Community Methods in Networks
140
0
0.0
(
0
)
تأليف
James P. Bagrow
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present a new benchmarking procedure that is unambiguous and specific to local community-finding methods, allowing one to compare the accuracy of various methods. We apply this to new and existing algorithms. A simple class of synthetic benchmark networks is also developed, capable of testing properties specific to these local methods.
قيم البحث
اقرأ أيضاً
In a network, we define shell $ell$ as the set of nodes at distance $ell$ with respect to a given node and define $r_ell$ as the fraction of nodes outside shell $ell$. In a transport process, information or disease usually diffuses from a random node
and reach nodes shell after shell. Thus, understanding the shell structure is crucial for the study of the transport property of networks. For a randomly connected network with given degree distribution, we derive analytically the degree distribution and average degree of the nodes residing outside shell $ell$ as a function of $r_ell$. Further, we find that $r_ell$ follows an iterative functional form $r_ell=phi(r_{ell-1})$, where $phi$ is expressed in terms of the generating function of the original degree distribution of the network. Our results can explain the power-law distribution of the number of nodes $B_ell$ found in shells with $ell$ larger than the network diameter $d$, which is the average distance between all pairs of nodes. For real world networks the theoretical prediction of $r_ell$ deviates from the empirical $r_ell$. We introduce a network correlation function $c(r_ell)equiv r_{ell+1}/phi(r_ell)$ to characterize the correlations in the network, where $r_{ell+1}$ is the empirical value and $phi(r_ell)$ is the theoretical prediction. $c(r_ell)=1$ indicates perfect agreement between empirical results and theory. We apply $c(r_ell)$ to several model and real world networks. We find that the networks fall into two distinct classes: (i) a class of {it poorly-connected} networks with $c(r_ell)>1$, which have larger average distances compared with randomly connected networks with the same degree distributions; and (ii) a class of {it well-connected} networks with $c(r_ell)<1$.
Structural changes in a network representation of a system (e.g.,different experimental conditions, time evolution), can provide insight on its organization, function and on how it responds to external perturbations. The deeper understanding of how g
ene networks cope with diseases and treatments is maybe the most incisive demonstration of the gains obtained through this differential network analysis point-of-view, which lead to an explosion of new numeric techniques in the last decade. However, {it where} to focus ones attention, or how to navigate through the differential structures can be overwhelming even for few experimental conditions. In this paper, we propose a theory and a methodological implementation for the characterization of shared structural roles of nodes simultaneously within and between networks, whose outcome is a highly {em interpretable} map. The main features and accuracy are investigated with numerical benchmarks generated by a stochastic block model. Results show that it can provide nuanced and interpretable information in scenarios with very different (i) community sizes and (ii) total number of communities, and (iii) even for a large number of 100 networks been compared (e.g., for 100 different experimental conditions). Then, we show evidence that the strength of the method is its story-telling-like characterization of the information encoded in a set of networks, which can be used to pinpoint unexpected differential structures, leading to further investigations and providing new insights. We provide an illustrative, exploratory analysis of four gene co-expression networks from two cell types $times$ two treatments (interferon-$beta$ stimulated or control). The method proposed here allowed us to elaborate and test a set of very specific hypotheses related to {em unique} and {em subtle} nuances of the structural differences between these networks.
The study of networks has grown into a substantial interdisciplinary endeavour that encompasses myriad disciplines in the natural, social, and information sciences. Here we introduce a framework for constructing taxonomies of networks based on their
structural similarities. These networks can arise from any of numerous sources: they can be empirical or synthetic, they can arise from multiple realizations of a single process, empirical or synthetic, or they can represent entirely different systems in different disciplines. Since the mesoscopic properties of networks are hypothesized to be important for network function, we base our comparisons on summaries of network community structures. While we use a specific method for uncovering network communities, much of the introduced framework is independent of that choice. After introducing the framework, we apply it to construct a taxonomy for 746 individual networks and demonstrate that our approach usefully identifies similar networks. We also construct taxonomies within individual categories of networks, and in each case we expose non-trivial structure. For example we create taxonomies for similarity networks constructed from both political voting data and financial data. We also construct network taxonomies to compare the social structures of 100 Facebook networks and the growth structures produced by different types of fungi.
Much recent empirical evidence shows that textit{community structure} is ubiquitous in the real-world networks. In this Letter, we propose a growth model to create scale-free networks with the tunable strength (noted by $Q$) of community structure an
d investigate the influence of community strength upon the collective synchronization induced by SIRS epidemiological process. Global and local synchronizability of the system is studied by means of an order parameter and the relevant finite-size scaling analysis is provided. The numerical results show that, a phase transition occurs at $Q_csimeq0.835$ from global synchronization to desynchronization and the local synchronization is weakened in a range of intermediately large $Q$. Moreover, we study the impact of mean degree $<k>$ upon synchronization on scale-free networks.
Community structures are critical towards understanding not only the network topology but also how the network functions. However, how to evaluate the quality of detected community structures is still challenging and remains unsolved. The most widely
used metric, normalized mutual information (NMI), was proved to have finite size effect, and its improved form relative normalized mutual information (rNMI) has reverse finite size effect. Corrected normalized mutual information (cNMI) was thus proposed and has neither finite size effect nor reverse finite size effect. However, in this paper we show that cNMI violates the so-called proportionality assumption. In addition, NMI-type metrics have the problem of ignoring importance of small communities. Finally, they cannot be used to evaluate a single community of interest. In this paper, we map the computed community labels to the ground-truth ones through integer linear programming, then use kappa index and F-score to evaluate the detected community structures. Experimental results demonstrate the advantages of our method.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
