Detecting overlapping communities in networks via dominant label propagation

Community detection is an important methodology for understanding the intrinsic structure and function of a realworld network. In this paper, we propose an effective and efficient algorithm, called Dominant Label Propagation Algorithm（Abbreviated as DLPA）, to detect communities in complex networks. The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously. Our algorithm is very efficient, since its computational complexity is almost linear to the number of edges in the network. Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.

Detecting Communities in K-Partite K-Uniform (Hyper)Networks

In social tagging systems such as Delicious and Flickr,users collaboratively manage tags to annotate resources.Naturally,a social tagging system can be modeled as a （user,tag,resource） hypernetwork,where there are three different types of nodes,namely users,resources and tags,and each hyperedge has three end nodes,connecting a user,a resource and a tag that the user employs to annotate the resource.Then how can we automatically cluster related users,resources and tags,respectively？ This is a problem of community detection in a 3-partite,3-uniform hypernetwork.More generally,given a K-partite K-uniform （hyper）network,where each （hyper）edge is a K-tuple composed of nodes of K different types,how can we automatically detect communities for nodes of different types？ In this paper,by turning this problem into a problem of finding an efficient compression of the （hyper）network＇s structure,we propose a quality function for measuring the goodness of partitions of a K-partite K-uniform （hyper）network into communities,and develop a fast community detection method based on optimization.Our method overcomes the limitations of state of the art techniques and has several desired properties such as comprehensive,parameter-free,and scalable.We compare our method with existing methods in both synthetic and real-world datasets.

Identifying Influential Communities Using IID for a Multilayer Networks

In online social networks(OSN),they generate several specific user activities daily,corresponding to the billions of data points shared.However,although users exhibit significant interest in social media,they are uninterested in the content,discussions,or opinions available on certain sites.Therefore,this study aims to identify influential communities and understand user behavior across networks in the information diffusion process.Social media platforms,such as Facebook and Twitter,extract data to analyze the information diffusion process,based on which they cascade information among the individuals in the network.Therefore,this study proposes an influential information diffusion model that identifies influential communities across these two social media sites.More-over,it addresses site migration by visualizing a set of overlapping communities using hyper-edge detection.Thus,the overlapping community structure is used to identify similar communities with identical user interests.Furthermore,the com-munity structure helps in determining the node activation and user influence from the information cascade model.Finally,the Fraction of Intra/Inter-Layer(FIL)dif-fusion score is used to evaluate the efficiency of the influential information diffu-sion model by analyzing the trending influential communities in a multilayer network.However,from the experimental result,it observes that the FIL diffusion score for the proposed method achieves better results in terms of accuracy,preci-sion,recall and efficiency of community detection than the existing methods.

Detecting community structure using label propagation with consensus weight in complex network

Community detection is a fundamental work to analyse the structural and functional properties of complex networks. The label propagation algorithm （LPA） is a near linear time algorithm to find a good community structure. Despite various subsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the basic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these consensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the edge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number of partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps, by computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter to adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an approach named the label propagation algorithm with consensus weight （LPAcw）, and the experimental results showed that the LPAcw could enhance considerably both the stability and the accuracy of community partitions.

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 Detection Using Jaacard Similarity with SIM-Edge Detection Techniques

The structure and dynamic nature of real-world networks can be revealed by communities that help in promotion of recommendation systems.Social Media platforms were initially developed for effective communication,but now it is being used widely for extending and to obtain profit among business community.The numerous data generated through these platforms are utilized by many companies that make a huge profit out of it.A giant network of people in social media is grouped together based on their similar properties to form a community.Commu-nity detection is recent topic among the research community due to the increase usage of online social network.Community is one of a significant property of a net-work that may have many communities which have similarity among them.Community detection technique play a vital role to discover similarities among the nodes and keep them strongly connected.Similar nodes in a network are grouped together in a single community.Communities can be merged together to avoid lot of groups if there exist more edges between them.Machine Learning algorithms use community detection to identify groups with common properties and thus for recommen-dation systems,health care assistance systems and many more.Considering the above,this paper presents alternative method SimEdge-CD(Similarity and Edge between's based Community Detection)for community detection.The two stages of SimEdge-CD initiallyfind the similarity among nodes and group them into one community.During the second stage,it identifies the exact affiliations of boundary nodes using edge betweenness to create well defined communities.Evaluation of proposed method on synthetic and real datasets proved to achieve a better accuracy-efficiency trade-of compared to other existing methods.Our proposed SimEdge-CD achieves ideal value of 1 which is higher than existing sim closure like LPA,Attractor,Leiden and walktrap techniques.

Dynamic evolutionary community detection algorithms based on the modularity matrix

Motivated by the relationship of the dynamic behaviors and network structure, in this paper, we present two efficient dynamic community detection algorithms. The phases of the nodes in the network can evolve according to our proposed differential equations. In each iteration, the phases of the nodes are controlled by several parameters. It is found that the phases of the nodes are ultimately clustered into several communities after a short period of evolution. They can be adopted to detect the communities successfully. The second differential equation can dynamically adjust several parameters, so it can obtain satisfactory detection results. Simulations on some test networks have verified the efficiency of the presented algorithms.

Spatial Structure of Urban Residents’ Leisure Activities: A Case Study of Shenyang, China

The spatial characteristics of residents’ leisure activities not only reflect their demand for urban leisure space but also affect the urban spatial layout. This study takes Shenyang, China as an example and analyzes the characteristics of residents’ leisure activities through questionnaires. On this basis, it uses point of interest data and mobile phone signaling data to identify various types of residential and leisure functional relationships, and uses spatial analysis and community detection to assess the distance characteristics, flow patterns, and community structure of residents’ leisure activities, so as to discuss the spatial structure of residents’ leisure activities in Shenyang. The results showed that: (1) in addition to leisure at home, Shenyang residents mainly went to shopping malls, supermarkets,and parks for leisure activities, and the proportions of residents of the two types of leisure activities were approximately equal;(2) the average distances that residents traveled for shopping and park leisure were near in the middle and far in the periphery, and the travel costs of peripheral residents for centrally located leisure were higher than those for residents in central areas;(3) the flow patterns of the residential-shopping and residential-park functional relationships displayed clustering mode characteristics, and Shenyang presented a significant monocentric structure;and (4) residents’ shopping activities were concentrated in the southern community, and walking in the park activities were concentrated in the western community. Residents’ leisure activities were characterized by centripetal agglomeration,which was prone to problems such as traffic congestion and big city diseases. The spatial expansion process in the city was characterized by obvious directional inheritance and path dependence, and the construction of sub-cities is needed to improve the related service facilities.

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.

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.

Detection of consensuses and treatment principles of diabetic nephropathy in traditional Chinese medicine: A new approach

Objective:To propose and test a new approach based on community detection in the field of social computing for uncovering consensuses and treatment principles in traditional Chinese medicine(TCM).Methods:Three Chinese databases(CNKI,VIP,andWan Fang Data)were searched for published articles on TCM treatment of diabetic nephropathy(DN)from their inception until September 31,2014.Zheng classification and herbdatawereextractedfromincluded articlesand usedto construct a Zheng classification and treatment of diabetic nephropathy(DNZCT)network with nodes denoting Zhengs and herbs and edges denoting corresponding treating relationshipsamong them.Community detection was applied to the DNZCT and detected community structures were analyzed.Results:A network of 201 nodes and 743 edges were constructed and six communities were detected.Nodes clustered in the samecommunity captured the samesemantic topic;different communities had unique characteristics,and indicated different treatment principles.Large communities usually represented similar points of view or consensuses on common Zheng diagnoses and herb prescriptions;small communities might help to indicate unusual Zhengs and herbs.Conclusion:The results suggest that the community detection-based approach is useful and feasible for uncovering consensuses and treatment principles of DN treatment in TCM,and could be used to address other similar problems in TCM.

Density-based rough set model for hesitant node clustering in overlapping community detection

Overlapping community detection in a network is a challenging issue which attracts lots of attention in recent years.A notion of hesitant node（HN） is proposed. An HN contacts with multiple communities while the communications are not strong or even accidental, thus the HN holds an implicit community structure.However, HNs are not rare in the real world network. It is important to identify them because they can be efficient hubs which form the overlapping portions of communities or simple attached nodes to some communities. Current approaches have difficulties in identifying and clustering HNs. A density-based rough set model（DBRSM） is proposed by combining the virtue of densitybased algorithms and rough set models. It incorporates the macro perspective of the community structure of the whole network and the micro perspective of the local information held by HNs, which would facilitate the further ＂growth＂ of HNs in community. We offer a theoretical support for this model from the point of strength of the trust path. The experiments on the real-world and synthetic datasets show the practical significance of analyzing and clustering the HNs based on DBRSM. Besides, the clustering based on DBRSM promotes the modularity optimization.

Alleviating the Cold Start Problem in Recommender Systems Based on Modularity Maximization Community Detection Algorithm

Recommender system (RS) has become a very important factor in many eCommerce sites. In our daily life, we rely on the recommendation from other persons either by word of mouth, recommendation letters, movie, item and book reviews printed in newspapers, etc. The typical Recommender Systems are software tools and techniques that provide support to people by identifying interesting products and services in online store. It also provides a recommendation for certain users who search for the recommendations. The most important open challenge in Collaborative filtering recommender system is the cold start problem. If the adequate or sufficient information is not available for a new item or users, the recommender system runs into the cold start problem. To increase the usefulness of collaborative recommender systems, it could be desirable to eliminate the challenge such as cold start problem. Revealing the community structures is crucial to understand and more important with the increasing popularity of online social networks. The community detection is a key issue in social network analysis in which nodes of the communities are tightly connected each other and loosely connected between other communities. Many algorithms like Givan-Newman algorithm, modularity maximization, leading eigenvector, walk trap, etc., are used to detect the communities in the networks. To test the community division is meaningful we define a quality function called modularity. Modularity is that the links within a community are higher than the expected links in those communities. In this paper, we try to give a solution to the cold-start problem based on community detection algorithm that extracts the community from the social networks and identifies the similar users on that network. Hence, within the proposed work several intrinsic details are taken as a rule of thumb to boost the results higher. Moreover, the simulation experiment was taken to solve the cold start problem.

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.

Community detection in signed networks based on discrete-time model

Community detection in signed networks has been studied widely in recent years. In this paper, a discrete difference equation is proposed to imitate the consistently changing phases of the nodes. During the interaction, each node will update its phase based on the difference equation. Each node has many different nodes connected with it, and these neighbors have different influences on it. The similarity between two nodes is applied to describe the influences between them. Nodes with high positive similarities will get together and nodes with negative similarities will be far away from each other.Communities are detected ultimately when the phases of the nodes are stable. Experiments on real world and synthetic signed networks show the efficiency of detection performance. Moreover, the presented method gains better detection performance than two existing good algorithms.

Homonyms Discovery in Folksonomy Based on User Community Analysis

to the capability of reflecting social perception on semantic of resources, folksonomy has been proposed to improve the social learning for education and scholar researching. However, its actual impact is significantly influenced by the semantic ambiguity problem of tags. So, in this paper, we proposed a novel way of detecting homonyms, one of the main sources of tag＇s semantic ambiguity problem, in noisy folksonomies. The study is based on two hypotheses： 1） Users having different interests tend to have different understanding of the same tag. 2） Users having similar interest tend to have common understanding of the same tag. Therefore, we firstly discover user communities according to users＇ interests. Then, tag contexts are discovered in subsets of folksonomy on the basis of user communities. The experimental results show that our method is effective and outperform the method finding tag contexts using all tags in folksonomy with overlapping clustering algorithm especially when various users having different interests are contained by the folksonomyo

Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

The statistical model for community detection is a promising research area in network analysis.Most existing statistical models of community detection are designed for networks with a known type of community structure,but in many practical situations,the types of community structures are unknown.To cope with unknown community structures,diverse types should be considered in one model.We propose a model that incorporates the latent interaction pattern,which is regarded as the basis of constructions of diverse community structures by us.The interaction pattern can parameterize various types of community structures in one model.A collapsed Gibbs sampling inference is proposed to estimate the community assignments and other hyper-parameters.With the Pitman-Yor process as a prior,our model can automatically detect the numbers and sizes of communities without a known type of community structure beforehand.Via Bayesian inference,our model can detect some hidden interaction patterns that offer extra information for network analysis.Experiments on networks with diverse community structures demonstrate that our model outperforms four state-of-the-art models.

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.

Modularity-based representation learning for networks

Network embedding aims at learning low-dimensional representation of vertexes in a network and effectively preserving network structures.These representations can be used as features for many complex tasks on networks such as community detection and multi-label classification.Some classic methods based on the skip-gram model have been proposed to learn the representation of vertexes.However,these methods do not consider the global structure(i.e.,community structure)while sampling vertex sequences in network.To solve this problem,we suggest a novel sampling method which takes community information into consideration.It first samples dense vertex sequences by taking advantage of modularity function and then learns vertex representation by using the skip-gram model.Experimental results on the tasks of community detection and multi-label classification show that our method outperforms three state-of-the-art methods on learning the vertex representations in networks.

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.