A genetic algorithm for community detection in complex networks

A new genetic algorithm for community detection in complex networks was proposed. It adopts matrix encoding that enables traditional crossover between individuals. Initial populations are generated using nodes similarity, which enhances the diversity of initial individuals while retaining an acceptable level of accuracy, and improves the efficiency of optimal solution search. Individual crossover is based on the quality of individuals' genes; all nodes unassigned to any community are grouped into a new community, while ambiguously placed nodes are assigned to the community to which most of their neighbors belong. Individual mutation, which splits a gene into two new genes or randomly fuses it into other genes, is non-uniform. The simplicity and effectiveness of the algorithm are revealed in experimental tests using artificial random networks and real networks. The accuracy of the algorithm is superior to that of some classic algorithms, and is comparable to that of some recent high-precision algorithms.

Mutually Enhancing Community Detection and Sentiment Analysis on Twitter Networks

The burgeoning use of Web 2.0-powered social media in recent years has inspired numerous studies on the content and composition of online social networks (OSNs). Many methods of harvesting useful information from social networks’ immense amounts of user-generated data have been successfully applied to such real-world topics as politics and marketing, to name just a few. This study presents a novel twist on two popular techniques for studying OSNs: community detection and sentiment analysis. Using sentiment classification to enhance community detection and community partitions to permit more in-depth analysis of sentiment data, these two techniques are brought together to analyze four networks from the Twitter OSN. The Twitter networks used for this study are extracted from four accounts related to Microsoft Corporation, and together encompass more than 60,000 users and 2 million tweets collected over a period of 32 days. By combining community detection and sentiment analysis, modularity values were increased for the community partitions detected in three of the four networks studied. Furthermore, data collected during the community detection process enabled more granular, community-level sentiment analysis on a specific topic referenced by users in the dataset.

SELF-ORGANIZING MAP OF COMPLEX NETWORKS FOR COMMUNITY DETECTION

Detecting communities from complex networks is an important issue and has attracted attention of researchers in many fields. It is relevant to social tasks, biological inquiries, and technological problems since various networks exist in these systems. This paper proposes a new self-organizing map （SOM） based approach to community detection. By adopting a new operation and a new weightupdating scheme, a complex network can be organized into dense subgraphs according to the topological connection of each node by the SOM algorithm. Extensive numerical experiments show that the performance of the SOM algorithm is good. It can identify communities more accurately than existing methods. This method can be used to detect communities not only in undirected networks, but also in directed networks and bipartite networks.

Enhancing Sentiment Analysis on Twitter Using Community Detection

The increasing popularity of social media in recent years has created new opportunities to study the interactions of different groups of people. Never before have so many data about such a large number of individuals been readily available for analysis. Two popular topics in the study of social networks are community detection and sentiment analysis. Community detection seeks to find groups of associated individuals within networks, and sentiment analysis attempts to determine how individuals are feeling. While these are generally treated as separate issues, this study takes an integrative approach and uses community detection output to enable community-level sentiment analysis. Community detection is performed using the Walktrap algorithm on a network of Twitter users associated with Microsoft Corporation’s @technet account. This Twitter account is one of several used by Microsoft Corporation primarily for communicating with information technology professionals. Once community detection is finished, sentiment in the tweets produced by each of the communities detected in this network is analyzed based on word sentiment scores from the well-known SentiWordNet lexicon. The combination of sentiment analysis with community detection permits multilevel exploration of sentiment information within the @technet network, and demonstrates the power of combining these two techniques.

The Influence Factors of Collective Intelligence Emergence in Knowledge Communities Based on Social Network Analysis

The advent of the age of Information shifts the environment we live in from off-line to on-line. The prospect of Collective Intelligence (CI) is promising. Based on this background, the aim of this paper is to discover the emergence mechanism and influence factors of CI in knowledge communities using the method of quantitative and qualitative analysis. On the basis of the previous research work, our model theorizes that the two dimensions of social network (i.e., interactive network structure and participant’s characteristics) affect two references of effectiveness (i.e. group knowledge production and participation of group decision). And this hypothetical model is validated with simulation data from “Zhihu” community. Our model has been useful since it offers some inspirations and directions to promote the level of CI in knowledge communities.

Research community detection from multi-relation researcher network based on structure/attribute similarities

Purpose: This paper aims to provide a method to detect research communities based on research interest in researcher network, which combines the topological structure and vertex attributes in a unified manner.Design/methodology/approach: A heterogeneous researcher network has been constructed by combining multiple relations of academic researchers. Vertex attributes and their similarities were considered and calculated. An approach has been proposed and tested to detect research community in research organizations based on this multi-relation researcher network.Findings: Detection of topologically well-connected, semantically coherent and meaningful research community was achieved.Research limitations: The sample size of evaluation experiments was relatively small. In the present study, a limited number of 72 researchers were analyzed for constructing researcher network and detecting research community. Therefore, a large sample size is required to give more information and reliable results.Practical implications: The proposed multi-relation researcher network and approaches for discovering research communities of similar research interests will contribute to collective innovation behavior such as brainstorming and to promote interdisciplinary cooperation.Originality/value: Recent researches on community detection devote most efforts to singlerelation researcher networks and put the main focus on the topological structure of networks.In reality, there exist multi-relation social networks. Vertex attribute also plays an important role in community detection. The present study combined multiple single-relational researcher networks into a multi-relational network and proposed a structure-attribute clustering method for detecting research community in research organizations.

AN IMPROVED GN ALGORITHM OF NETWORK COMMUNITY DETECTION METHOD

.GN algorithm has high classification accuracy on community detection, but its time complexity is too high. In large scale network, the algorithm is lack of practical values. This paper puts forward an improved GN algorithm. The algorithm firstly get the network center nodes set, then use the shortest paths between center nodes and other nodes to calculate the edge betweenness, and then use incremental module degree as the algorithm terminates standard. Experiments show that, the new algorithm not only ensures accuracy of network community division, but also greatly reduced the time complexity, and improves the efficiency of community division.

Seed-Oriented Local Community Detection Based on Influence Spreading

In recent years,local community detection algorithms have developed rapidly because of their nearly linear computing time and the convenience of obtaining the local information of real-world networks.However,there are still some issues that need to be further studied.First,there is no local community detection algorithm dedicated to detecting a seed-oriented local community,that is,the local community with the seed as the core.The second and third issues are that the quality of local communities detected by the previous local community detection algorithms are largely dependent on the position of the seed and predefined parameters,respectively.To solve the existing problems,we propose a seed-oriented local community detection algorithm,named SOLCD,that is based on influence spreading.First,we propose a novel measure of node influence named k-core centrality that is based on the k-core value of adjacent nodes.Second,we obtain the seed-oriented local community,which is composed of the may-members and the must-member chain of the seed,by detecting the influence scope of the seed.The may-members and the must-members of the seed are determined by judging the influence relationship between the node and the seed.Five state-of-art algorithms are compared to SOLCD on six real-world networks and three groups of artificial networks.The experimental results show that SOLCD can achieve a high-quality seed-oriented local community for various real-world networks and artificial networks with different parameters.In addition,when taking nodes with different influence as seeds,SOLCD can stably obtain high-quality seed-oriented local communities.

Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks

In this paper, we propose a balanced multi-label propagation algorithm （BMLPA） for overlapping community detection in social networks. As well as its fast speed, another important advantage of our method is good stability, which other multi-label propagation algorithms, such as COPRA, lack. In BMLPA, we propose a new update strategy, which requires that community identifiers of one vertex should have balanced belonging coefficients. The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships, which is needed for COPRA. Also, we propose a fast method to generate ＂rough cores＂, which can be used to initialize labels for multi-label propagation algorithms, and are able to improve the quality and stability of results. Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.

Refactoring Software Packages via Community Detection in Complex Software Networks

An intrinsic property of software in a real-world environment is its need to evolve, which is usually accompanied by the increase of software complexity and deterioration of software quality, making software maintenance a tough problem. Refactoring is regarded as an effective way to address this problem. Many refactoring approaches at the method and class level have been proposed. But the research on software refactoring at the package level is very little. This paper presents a novel approach to refactor the package structures of object oriented software. It uses software networks to represent classes and their dependencies. It proposes a constrained community detection algorithm to obtain the optimized community structures in software networks, which also correspond to the optimized package structures. And it finally provides a list of classes as refactoring candidates by comparing the optimized package structures with the real package structures. The empirical evaluation of the proposed approach has been performed in two open source Java projects, and the benefits of our approach are illustrated in comparison with the other three approaches.

Community Detection in Complex Networks

With the rapidly growing evidence that various systems in nature and society can be modeled as complex networks, community detection in networks becomes a hot research topic in physics sociology, computer society, etc. Although this investigation of community structures has motivated many diverse algorithms, most of them are unsuitable when dealing with large networks due to their computational cost. In this paper, we present a faster algorithm ComTector which is more efficient for the community detection in large complex networks based on the nature of overlapping cliques. This algorithm does not require any priori knowledge about the number or the original division of the communities. With respect to practical applications, ComTector is challenging with five different types of networks including the classic Zachary Karate Club, Scientific Collaboration Network South Florida Free Word Association Network, Urban Traffic Network North America Power Grid and the Telecommunication Call Network. Experimental results show that our algorithm can discover meaningful communities that meet both the objective basis and our intuitions.

Decoding rural connections:A comparative insight into social network analysis in rural communities of China and beyond

Social Network Theory and methods have emerged as pivotal tools for dissecting intricate interdisciplinary issues in rural communities.This study aims to systematically delineate the application characteristics and trends of Social Network Analysis(SNA)in rural community research.Using a twofold approach,we integrate a traditional literature review and CiteSpace bibliometric analysis to assess the application status and evolutionary trends of SNA methods in this context.The key findings include the following:①Chinese research trends:scholars predominantly concentrate on the“three rural”issues(related to agriculture,rural areas,and small-scale farmers)and social support mechanisms for vulnerable rural populations.With policy shifts,rural revitalization,tourism,governance,social trust,and multi-dimensional poverty are poised to emerge as hot topics for the future.For further refinement,we suggest that the application of SNA in rural community research could benefit from content expansion,long-term studies,and innovative modelling techniques.②Research by international scholars has been primarily directed toward the physical and mental health of rural residents,as well as socioeconomic issues.Despite these studies covering a range of typical cases across various nations,a conspicuous lack of thorough,systematic,and prolonged efforts focused on rural community development in specific regions remains.Additionally,health issues affecting rural residents are expected to sustain long-standing and focused international academic attention.This study contributes to a more nuanced understanding of the current applications and potential future directions of SNA in rural community studies,both in China and internationally.

Community Detection in Dynamic Social Networks

There are many community detection algorithms for discovering communities in networks, but very few deal with networks that change structure. The SCAN (Structural Clustering Algorithm for Networks) algorithm is one of these algorithms that detect communities in static networks. To make SCAN more effective for the dynamic social networks that are continually changing their structure, we propose the algorithm DSCAN (Dynamic SCAN) which improves SCAN to allow it to update a local structure in less time than it would to run SCAN on the entire network. We also improve SCAN by removing the need for parameter tuning. DSCAN, tested on real world dynamic networks, performs faster and comparably to SCAN from one timestamp to another, relative to the size of the change. We also devised an approach to genetic algorithms for detecting communities in dynamic social networks, which performs well in speed and modularity.

Advanced Community Identification Model for Social Networks

Community detection in social networks is a hard problem because of the size,and the need of a deep understanding of network structure and functions.While several methods with significant effort in this direction have been devised,an outstanding open problem is the unknown number of communities,it is generally believed that the role of influential nodes that are surrounded by neighbors is very important.In addition,the similarity among nodes inside the same cluster is greater than among nodes from other clusters.Lately,the global and local methods of community detection have been getting more attention.Therefore,in this study,we propose an advanced communitydetection model for social networks in order to identify network communities based on global and local information.Our proposed model initially detects the most influential nodes by using an Eigen score then performs local expansion powered by label propagation.This process is conducted with the same color till nodes reach maximum similarity.Finally,the communities are formed,and a clear community graph is displayed to the user.Our proposed model is completely parameter-free,and therefore,no prior information is required,such as the number of communities,etc.We perform simulations and experiments using well-known synthetic and real network benchmarks,and compare them with well-known state-of-the-art models.The results prove that our model is efficient in all aspects,because it quickly identifies communities in the network.Moreover,it can easily be used for friendship recommendations or in business recommendation systems.

Contextualized Analysis of Social Networks:Collaboration in Scientific Communities

Currently, the collaboration in scientific communities has been studied in order to explain, among other things, the knowledge diffusion. The quality of Graduate Programmes is often associated with the scientific collaboration. This paper discusses how scientific collaboration processes can be identified and characterized through social and complex networks. For this purpose, collaboration networks of bibliographic production, research projects, and committees of PhD theses and Masters’ dissertations by researchers from a graduate program in computational modeling were studied. The data were obtained from CAPES’ reports of the period from 2001 to 2009. Among the studied indices, centrality indices indicate the presence of prominent researchers who influence others and promptly interact with other researchers in the network. The indices of complex networks reveal the presence of the small-world (i.e. these networks are favorable to increase coordination between researchers) phenomenon and indicate a behavior of scale-free degree distribution (i.e. some researchers promote clustering more than others) for one of the studied networks.

An Improved Harris Hawks Optimization Algorithm with Multi-strategy for Community Detection in Social Network

The purpose of community detection in complex networks is to identify the structural location of nodes. Complex network methods are usually graphical, with graph nodes representing objects and edges representing connections between things. Communities are node clusters with many internal links but minimal intergroup connections. Although community detection has attracted much attention in social media research, most face functional weaknesses because the structure of society is unclear or the characteristics of nodes in society are not the same. Also, many existing algorithms have complex and costly calculations. This paper proposes different Harris Hawk Optimization (HHO) algorithm methods (such as Improved HHO Opposition-Based Learning(OBL) (IHHOOBL), Improved HHO Lévy Flight (IHHOLF), and Improved HHO Chaotic Map (IHHOCM)) were designed to balance exploitation and exploration in this algorithm for community detection in the social network. The proposed methods are evaluated on 12 different datasets based on NMI and modularity criteria. The findings reveal that the IHHOOBL method has better detection accuracy than IHHOLF and IHHOCM. Also, to offer the efficiency of the , state-of-the-art algorithms have been used as comparisons. The improvement percentage of IHHOOBL compared to the state-of-the-art algorithm is about 7.18%.

Identifying influential nodes in social networks via community structure and influence distribution difference

This paper aims to effectively solve the problem of the influence maximization in social networks.For this purpose,an influence maximization method that can identify influential nodes via the community structure and the influence distribution difference is proposed.Firstly,the network embedding-based community detection approach is developed,by which the social network is divided into several high-quality communities.Secondly,the solution of influence maximization is composed of the candidate stage and the greedy stage.The candidate stage is to select candidate nodes from the interior and the boundary of each community using a heuristic algorithm,and the greedy stage is to determine seed nodes with the largest marginal influence increment from the candidate set through the sub-modular property-based Greedy algorithm.Finally,experimental results demonstrate the superiority of the proposed method compared with existing methods,from which one can further find that our work can achieve a good tradeoff between the influence spread and the running time.

Graph Transformer for Communities Detection in Social Networks

Graphs are used in various disciplines such as telecommunication,biological networks,as well as social networks.In large-scale networks,it is challenging to detect the communities by learning the distinct properties of the graph.As deep learning hasmade contributions in a variety of domains,we try to use deep learning techniques to mine the knowledge from large-scale graph networks.In this paper,we aim to provide a strategy for detecting communities using deep autoencoders and obtain generic neural attention to graphs.The advantages of neural attention are widely seen in the field of NLP and computer vision,which has low computational complexity for large-scale graphs.The contributions of the paper are summarized as follows.Firstly,a transformer is utilized to downsample the first-order proximities of the graph into a latent space,which can result in the structural properties and eventually assist in detecting the communities.Secondly,the fine-tuning task is conducted by tuning variant hyperparameters cautiously,which is applied to multiple social networks(Facebook and Twitch).Furthermore,the objective function(crossentropy)is tuned by L0 regularization.Lastly,the reconstructed model forms communities that present the relationship between the groups.The proposed robust model provides good generalization and is applicable to obtaining not only the community structures in social networks but also the node classification.The proposed graph-transformer shows advanced performance on the social networks with the average NMIs of 0.67±0.04,0.198±0.02,0.228±0.02,and 0.68±0.03 on Wikipedia crocodiles,Github Developers,Twitch England,and Facebook Page-Page networks,respectively.

Community Discovery with Location-Interaction Disparity in Mobile Social Networks

With the fast-growth of mobile social network, people＇ s interactions are frequently marked with location information, such as longitude and latitude of visited base station. This boom of data has led to considerable interest in research fields such as user behavior mining, trajectory discovery and social demographics. However, there is little research on community discovery in mobile social networks, and this is the problem this work tackles with. In this work, we take advantage of one simple property that people in different locations often belong to different social circles in order to discover communities in these networks. Based on this property, which we referred to as Location-lnteraction Disparity （LID）, we proposed a state network and then define a quality function evaluating community detection results. We also propose a hybrid community- detection algorithm using LID tor discovering location-based communities effectively and efficiently. Experiments on synthesis networks show that this algorithm can run effectively in time and discover communities with high precision. In realworld networks, the method reveals people＇s different social circles in different places with high efficiency.

A Community Detection Algorithm Based on Markov Random Walks Ants in Complex Network

Complex networks display community structures. Nodes within groups are densely connected but among groups are sparsely connected. In this paper, an algorithm is presented for community detection named Markov Random Walks Ants(MRWA). The algorithm is inspired by Markov random walks model theory, and the probability of ants located in any node within a cluster will be greater than that located outside the cluster.Through the random walks, the network structure is revealed. The algorithm is a stochastic method which uses the information collected during the traverses of the ants in the network. The algorithm is validated on different datasets including computer-generated networks and real-world networks. The outcome shows the algorithm performs moderately quickly when providing an acceptable time complexity and its result appears good in practice.