Detecting overlapping communities based on vital nodes in complex networks

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm（DOCBVA）, an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.

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.

Set pair three-way overlapping community discovery algorithm for weighted social internet of things

There are many problems in Social Internet of Things(IoTs),such as complex topology information,different degree of association between nodes and overlapping communities.The idea of set pair information grain computing and clustering is introduced to solve the above problems so as to accurately describe the similarity between nodes and fully explore the multi-community structure.A Set Pair Three-Way Overlapping Community Discovery Algorithm for Weighted Social Internet of Things(WSIoT-SPTOCD)is proposed.In the local network structure,which fully considers the topological information between nodes,the set pair connection degree is used to analyze the identity,difference and reverse of neighbor nodes.The similarity degree of different neighbor nodes is defined from network edge weight and node degree,and the similarity measurement method of set pair between nodes based on the local information structure is proposed.According to the number of nodes'neighbors and the connection degree of adjacent edges,the clustering intensity of nodes is defined,and an improved algorithm for initial value selection of k-means is proposed.The nodes are allocated according to the set pair similarity between nodes and different communities.Three-way community structures composed of a positive domain,boundary domain and negative domain are generated iteratively.Next,the overlapping node set is generated according to the calculation results of community node membership.Finally,experiments are carried out on artificial networks and real networks.The results show that WSIoT-SPTOCD performs well in terms of standardized mutual information,overlapping community modularity and F1.

A local fuzzy method based on “p-strong” community for detecting communities in networks

In this paper,we propose a local fuzzy method based on the idea of ＂p-strong＂ community to detect the disjoint and overlapping communities in networks.In the method,a refined agglomeration rule is designed for agglomerating nodes into local communities,and the overlapping nodes are detected based on the idea of making each community strong.We propose a contribution coefficient bvcito measure the contribution of an overlapping node to each of its belonging communities,and the fuzzy coefficients of the overlapping node can be obtained by normalizing the bvci to all its belonging communities.The running time of our method is analyzed and varies linearly with network size.We investigate our method on the computergenerated networks and real networks.The testing results indicate that the accuracy of our method in detecting disjoint communities is higher than those of the existing local methods and our method is efficient for detecting the overlapping nodes with fuzzy coefficients.Furthermore,the local optimizing scheme used in our method allows us to partly solve the resolution problem of the global modularity.

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.

Structural Insights on Internet Traffic:Community Overlapping and Correlations

There is an increasing number of Internet applications, which leads to an increasing network capacity and availability. Internet traffic characterisation and application identification are, therefore, more important for efficient network management. In this paper, we construct flow graphs from detailed Internet traffic data collected from the public networks of Internet Service Providers. We analyse the community structures of the flow graph that is naturally formed by different applications. The community size, degree distribution of the community, and community overlap of 10 Internet applications are investigated. We further study the correlations between the communities from different applications. Our results provide deep insights into the behaviour Internet applications and traffic, which is helpful for both network management and user behaviour analysis.

Research on Community Structure in Bus Transport Networks

We abstract the bus transport networks(BTNs)to two kinds of complex networks with space L and spaceP methods respectively.Using improved community detecting algorithm(PKM agglomerative algorithm),we analyzethe community property of two kinds of BTNs graphs.The results show that the BTNs graph described with space Lmethod have obvious community property,but the other kind of BTNs graph described with space P method have not.The reason is that the BTNs graph described with space P method have the intense overlapping community propertyand general community division algorithms can not identify this kind of community structure.To overcome this problem,we propose a novel community structure called N-depth community and present a corresponding community detectingalgorithm,which can detect overlapping community.Applying the novel community structure and detecting algorithmto a BTN evolution model described with space P,whose network property agrees well with real BTNs',we get obviouscommunity property.

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.

Estimating posterior inference quality of the relational infinite latent feature model for overlapping community detection

Overlapping community detection has become a very hot research topic in recent decades,and a plethora of methods have been proposed.But,a common challenge in many existing overlapping community detection approaches is that the number of communities K must be predefined manually.We propose a flexible nonparametric Bayesian generative model for count-value networks,which can allow K to increase as more and more data are encountered instead of to be fixed in advance.The Indian buffet process was used to model the community assignment matrix Z,and an uncol-lapsed Gibbs sampler has been derived.However,as the community assignment matrix Zis a structured multi-variable parameter,how to summarize the posterior inference results andestimate the inference quality about Z,is still a considerable challenge in the literature.In this paper,a graph convolutional neural network based graph classifier was utilized to help tosummarize the results and to estimate the inference qualityabout Z.We conduct extensive experiments on synthetic data and real data,and find that empirically,the traditional posterior summarization strategy is reliable.

LBLP:Link-Clustering-Based Approach for Overlapping Community Detection

Recently, complex networks have attracted considerable research attention. Community detection is an important problem in the field of complex networks and is useful in a variety of applications such as information propagation, link prediction, recommendation, and marketing. In this study, we focus on discovering overlapping community structures by using link partitions. We propose a Latent Dirichlet Allocation （LDA）-Based Link Partition （LBLP） method, which can find communities with an adjustable range of overlapping. This method employs the LDA model to detect link partitions, which can calculate the community belonging factor for each link. On the basis of this factor, link partitions with bridge links can be found efficiently. We validate the effectiveness of the proposed solution by using both real-world and synthesized networks. The experimental results demonstrate that the approach can find a meaningful and relevant link community structure.