Many algorithms have been developed to detect communities in networks. The success of these developed algorithms varies according to the types of networks. A communitydetection algorithm cannot always guarantee the b...
详细信息
Many algorithms have been developed to detect communities in networks. The success of these developed algorithms varies according to the types of networks. A communitydetection algorithm cannot always guarantee the best results on all networks. The most important reason for this is the approach algorithms follow when dividing any network into communities (sub-networks). The modularity of the network determines the quality of communities in networks. It is concluded that networks with high modularity values are divided into more successful communities (clusters, sub-networks). This study proposes a modularity optimization algorithm to increase clustering success in any network without being dependent on any communitydetection algorithm. The basic approach of the proposed algorithm is to transfer nodes at the community boundary to neighboring communities if they meet the specified conditions. The method called KO (Karci-Oztemiz) optimization algorithm maximizes the modularity value of any communitydetection algorithm in the best case, while it does not change the modularity value in the worst case. For the KO algorithm's test, in this study, Walktrap, Cluster Edge Betweenness, Label Propagation, Fast Greedy, and Leading Eigenvector community detection algorithms have been applied on three popular networks that were unweighted and undirected previously used in the literature. The community structures created by five community detection algorithms were optimized via the KO algorithm and the success of the proposed method was analyzed. When the results are examined, the modularity values of the community detection algorithms applied on the three different networks have increased at varying rates (0%,.,14.73%).
The understanding, analysis, and prediction of the behaviours and dynamics of networks associated with several disciplines in sociology, criminology, biology, medicine, communication, economics, and academics have adv...
详细信息
ISBN:
(纸本)9783031744426;9783031744433
The understanding, analysis, and prediction of the behaviours and dynamics of networks associated with several disciplines in sociology, criminology, biology, medicine, communication, economics, and academics have advanced significantly because of the discovery of community structure. Finding communities and grouping them together is a useful first step in figuring out the behavioural patterns and structural characteristics of social networks. Many educational approaches have recently gradually embraced online learning, which raises several concerns regarding how to evaluate students' participation, teamwork, and behaviours in the brand-new, emergent learning communities. In this research work we have applied five algorithms of communitydetection on three different data set related to social network and online learning environment. The purpose of this work is to evaluate how communitydetection techniques are applied to network structure analysis in online learning environments. Experimental results indicate that the Girvan-newman and Louvain algorithm are giving the better results for communitydetection.
Social media echo chambers are known to be common sources of misinformation and harmful ideologies that have detrimental impacts on society. Therefore, techniques to detect echo chambers are of great significance. Rei...
详细信息
ISBN:
(纸本)9789819722655;9789819722662
Social media echo chambers are known to be common sources of misinformation and harmful ideologies that have detrimental impacts on society. Therefore, techniques to detect echo chambers are of great significance. Reinforcement of supporting opinions and rejection of dissenting opinions are two significant echo chamber properties that help detecting them in social networks. However, existing echo chamber detection methods do not capture the opinion rejection behaviour, which leads to poor echo chamber detection accuracy. Measures used by them do not facilitate quantifying both properties simultaneously while preserving the connectivity between echo chamber members. To address this problem, we propose a new measure, Signed Echo (SEcho) that quantifies opinion reinforcement and rejection properties of echo chambers and an echo chamber detection algorithm, Signed Echo detection Algorithm (SEDA) based on this measure, which preserves the connectivity among echo chamber members. The experimental results for real-world data show that SEDA outperforms the state-of-the-art echo chamber detection methods in detecting the communities with echo chamber properties, such as reinforcement of supporting opinions, rejection of dissenting opinions, connectivity between community members, spread of mis/disinformation and emotional contagion.
Most of the current complex networks that are of interest to practitioners possess a certain community structure that plays an important role in understanding the properties of these networks. For instance, a closely ...
详细信息
Most of the current complex networks that are of interest to practitioners possess a certain community structure that plays an important role in understanding the properties of these networks. For instance, a closely connected social communities exhibit faster rate of transmission of information in comparison to loosely connected communities. Moreover, many machine learning algorithms and tools that are developed for complex networks try to take advantage of the existence of communities to improve their performance or speed. As a result, there are many competing algorithms for detecting communities in large networks. Unfortunately, these algorithms are often quite sensitive and so they cannot be fine-tuned for a given, but a constantly changing, real-world network at hand. It is therefore important to test these algorithms for various scenarios that can only be done using synthetic graphs that have built-in community structure, power law degree distribution, and other typical properties observed in complex networks. The standard and extensively used method for generating artificial networks is the LFR graph generator. Unfortunately, this model has some scalability limitations and it is challenging to analyze it theoretically. Finally, the mixing parameter mu, the main parameter of the model guiding the strength of the communities, has a non-obvious interpretation and so can lead to unnaturally defined networks. In this paper, we provide an alternative random graph model with community structure and power law distribution for both degrees and community sizes, the Artificial Benchmark for communitydetection (ABCD graph). The model generates graphs with similar properties as the LFR one, and its main parameter xi can be tuned to mimic its counterpart in the LFR model, the mixing parameter mu. We show that the new model solves the three issues identified above and more. In particular, we test the speed of our algorithm and do a number of experiments comparing basic pro
Discovering the risks posed by software vulnerabilities is a challenge. Software vulnerabilities are often not listed and studies have shown 50.3% of the reports do not include the list of vulnerable libraries. Thus, ...
详细信息
Computing betweenness centrality (BC) in large graphs is crucial for various applications, including telecommunications, social, and biological networks. However, the huge size of the data presents significant challen...
详细信息
Computing betweenness centrality (BC) in large graphs is crucial for various applications, including telecommunications, social, and biological networks. However, the huge size of the data presents significant challenges. In this paper, we introduce a novel approximate approach for efficiently extracting top k BC nodes by combining the Louvain communitydetection algorithm with Brandes' algorithm. Our method significantly enhances the runtime efficiency of the traditional Brandes' algorithm while preserving accuracy across both synthetic and real-world datasets. Additionally, our approach is suitable for parallelization, further improving its efficiency. Experimental results confirm the effectiveness of our method for large and sparse graphs.
We report on the construction of a granular network of particles to study the formation, evolution, and statistical properties of clusters of particles developing at the vicinity of a liquid-solid-like phase transitio...
详细信息
We report on the construction of a granular network of particles to study the formation, evolution, and statistical properties of clusters of particles developing at the vicinity of a liquid-solid-like phase transition within a vertically vibrated quasi-two-dimensional granular system. Using the data of particle positions and local order from Castillo et al. [G. Castillo, N. Mujica, and R. Soto, Phys. Rev. Lett. 109, 095701 (2012)], we extract granular clusters taken as communities of the granular network via modularity optimization. Each one of these communities is a patch of particles with a very well defined local orientational order embedded within an array of other patches forming a complex cluster network. The distributions of cluster sizes and lifespans for the cluster network depend on the distance to the liquid-solid-like phase transition of the quasi-two-dimensional granular system. Specifically, the cluster size distribution displays a scale-invariant behavior for at least a decade in cluster sizes, while cluster lifespans grow monotonically with each cluster size. We believe this systematic community analysis for clustering in granular systems can help to study and understand the spatiotemporal evolution of mesoscale structures in systems displaying out-of-equilibrium phase transitions.
communitydetection is a classic network problem with extensive applications in various fields. Its most common method is using modularity maximization heuristics which rarely return an optimal partition or anything s...
详细信息
communitydetection is a classic network problem with extensive applications in various fields. Its most common method is using modularity maximization heuristics which rarely return an optimal partition or anything similar. Partitions with globally optimal modularity are difficult to compute, and therefore have been underexplored. Using structurally diverse networks, we compare 30 communitydetection methods including our proposed algorithm that offers optimality and approximation guarantees: the Bayan algorithm. Unlike existing methods, Bayan globally maximizes modularity or approximates it within a factor. Our results show the distinctive accuracy and stability of maximum-modularity partitions in retrieving planted partitions at rates higher than most alternatives for a wide range of parameter settings in two standard benchmarks. Compared to the partitions from 29 other algorithms, maximum-modularity partitions have the best medians for description length, coverage, performance, average conductance, and well clusteredness. These advantages come at the cost of additional computations which Bayan makes possible for small networks (networks that have up to 3000 edges in their largest connected component). Bayan is several times faster than using open-source and commercial solvers for modularity maximization, making it capable of finding optimal partitions for instances that cannot be optimized by any other existing method. Our results point to a few well-performing algorithms, among which Bayan stands out as the most reliable method for small networks. A python implementation of the Bayan algorithm (bayanpy) is publicly available through the package installer for python.
Mutual information is commonly used as a measure of similarity between competing labelings of a given set of objects, for example to quantify performance in classification and communitydetection tasks. As argued rece...
详细信息
Mutual information is commonly used as a measure of similarity between competing labelings of a given set of objects, for example to quantify performance in classification and communitydetection tasks. As argued recently, however, the mutual information as conventionally defined can return biased results because it neglects the information cost of the so-called contingency table, a crucial component of the similarity calculation. In principle the bias can be rectified by subtracting the appropriate information cost, leading to the modified measure known as the reduced mutual information, but in practice one can only ever compute an upper bound on this information cost, and the value of the reduced mutual information depends crucially on how good a bound is established. In this paper we describe an improved method for encoding contingency tables that gives a substantially better bound in typical use cases and approaches the ideal value in the common case where the labelings are closely similar, as we demonstrate with extensive numerical results.
This article presents a new look at the problem of finding reservoirs-analogues, representing reservoirs as a network and solving the problem of finding reservoirs-analogues as a problem of finding communities in the ...
详细信息
ISBN:
(纸本)9783031087547;9783031087530
This article presents a new look at the problem of finding reservoirs-analogues, representing reservoirs as a network and solving the problem of finding reservoirs-analogues as a problem of finding communities in the network. The proposed network approach allows us to effectively search for a cluster of reservoirs-analogues and restore missing parameters in the target reservoir based on the found clusters of reservoirs-analogues. Also, the network approach was compared with the baseline approach and showed greater efficiency. Three approaches were also compared to restore gaps in the target reservoir using clusters of reservoirs-analogues.
暂无评论