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.

A Core Leader Based Label Propagation Algorithm for Community Detection

A large number of community discovery algorithms have been proposed in the last decade. Recently, the sharp increase of network scale has become a great challenge for traditional community discovery algorithms. Label propagation algorithm is a semi-supervised machine learning method, which has linear time complexity when coping with large scale networks. However, the output result has less stability and the quality of the output communities still remains to be improved. Therefore, we propose a novel coreleader based label propagation algorithm for community detection called CLBLPA. Firstly, we find core leaders of potential community by using a greedy method. Then we utilize the label influence potential to guide the process of label propagation. Thus we can accelerate the convergence of algorithm and improve the stability of the output. Experimental results on synthetic datasets and real networks show that CLBLPA can significantly improve the quality of the output communities.

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.

DHSEGATs:distance and hop-wise structures encoding enhanced graph attention networks

Numerous works prove that existing neighbor-averaging graph neural networks(GNNs)cannot efficiently catch structure features,and many works show that injecting structure,distance,position,or spatial features can significantly improve the performance of GNNs,however,injecting high-level structure and distance into GNNs is an intuitive but untouched idea.This work sheds light on this issue and proposes a scheme to enhance graph attention networks(GATs)by encoding distance and hop-wise structure statistics.Firstly,the hop-wise structure and distributional distance information are extracted based on several hop-wise ego-nets of every target node.Secondly,the derived structure information,distance information,and intrinsic features are encoded into the same vector space and then added together to get initial embedding vectors.Thirdly,the derived embedding vectors are fed into GATs,such as GAT and adaptive graph diffusion network(AGDN)to get the soft labels.Fourthly,the soft labels are fed into correct and smooth(C&S)to conduct label propagation and get final predictions.Experiments show that the distance and hop-wise structures encoding enhanced graph attention networks(DHSEGATs)achieve a competitive result.

CPL:Detecting Protein Complexes by Propagating Labels on Protein-Protein Interaction Network

Proteins usually bind together to form complexes, which play an important role in cellular activities. Many graph clustering methods have been proposed to identify protein complexes by finding dense regions in protein-protein interaction networks. We present a novel framework （CPL） that detects protein complexes by propagating labels through interactions in a network, in which labels denote complex identifiers. With proper propagation in CPL, proteins in the same complex will be assigned with the same labels. CPL does not make any strong assumptions about the topological structures of the complexes, as in previous methods. Tile CPL algorithm is tested on several publicly available yeast protein-protein interaction networks and compared with several state-of-the-art methods. The results suggest that CPL performs better than the existing methods. An analysis of the functional homogeneity based on a gene ontology analysis shows that the detected complexes of CPL are highly biologically relevant.

Semi-supervised dictionary learning with label propagation for image classification

Sparse coding and supervised dictionary learning have rapidly developed in recent years,and achieved impressive performance in image classification. However, there is usually a limited number of labeled training samples and a huge amount of unlabeled data in practical image classification,which degrades the discrimination of the learned dictionary. How to effectively utilize unlabeled training data and explore the information hidden in unlabeled data has drawn much attention of researchers. In this paper, we propose a novel discriminative semisupervised dictionary learning method using label propagation(SSD-LP). Specifically, we utilize a label propagation algorithm based on class-specific reconstruction errors to accurately estimate the identities of unlabeled training samples, and develop an algorithm for optimizing the discriminative dictionary and discriminative coding vectors simultaneously.Extensive experiments on face recognition, digit recognition, and texture classification demonstrate the effectiveness of the proposed method.

Learning Noun Phrase Anaphoricity in Coreference Resolution via Label Propagation

Knowledge of noun phrase anaphoricity might be profitably exploited in coreference resolution to bypass the resolution of non-anaphoric noun phrases. However, it is surprising to notice that recent attempts to incorporate automatically acquired anaphoricity information into coreferenee resolution systems have been far from expectation. This paper proposes a global learning method in determining the anaphoricity of noun phrases via a label propagation algorithm to improve learning-based coreference resolution. In order to eliminate the huge computational burden in the label propagation algorithm, we employ the weighted support vectors as the critical instances in the training texts. In addition, two kinds of kernels, i.e instances to represent all the anaphoricity-labeled NP , the feature-based RBF （Radial Basis Function） kernel and the convolution tree kernel with approximate matching, are explored to compute the anaphoricity similarity between two noun phrases. Experiments on the ACE2003 corpus demonstrate the great effectiveness of our method in anaphoricity determination of noun phrases and its application in learning-based coreference resolution.

Identifying Propagation Source in Temporal Networks Based on Label Propagation

The spread of rumors and diseases threatens the development of society,it is of great practical significance to locate propagation source quickly and accurately when rumors or epidemic outbreaks occur.However,the topological structure of online social network changes with time,which makes it very difficult to locate the propagation source.There are few studies focus on propagation source identification in dynamic networks.However,it is usually necessary to know the propagation model in advance.In this paper the label propagation algorithm is proposed to locate propagation source in temporal network.Then the propagation source was identified by hierarchical processing of dynamic networks and label propagation backwards without any underlying information dissemination model.Different propagation models were applied for comparative experiments on static and dynamic networks.Experimental results verify the effectiveness of the algorithm on temporal networks.

A survey of recent interactive image segmentation methods

Image segmentation is one of the most basic tasks in computer vision and remains an initial step of many applications. In this paper, we focus on interactive image segmentation(IIS), often referred to as foreground–background separation or object extraction, guided by user interaction. We provide an overview of the IIS literature by covering more than 150 publications, especially recent works that have not been surveyed before. Moreover, we try to give a comprehensive classification of them according to different viewpoints and present a general and concise comparison of the most recent published works. Furthermore, we survey widely used datasets,evaluation metrics, and available resources in the field of IIS.

Semi-supervised non-negative Tucker decomposition for tensor data representation

Non-negative Tucker decomposition(NTD) has been developed as a crucial method for non-negative tensor data representation.However, NTD is essentially an unsupervised method and cannot take advantage of label information. In this paper, we claim that the low-dimensional representation extracted by NTD can be treated as the predicted soft-clustering coefficient matrix and can therefore be learned jointly with label propagation in a unified framework. The proposed method can extract the physicallymeaningful and parts-based representation of tensor data in their natural form while fully exploring the potential ability of the given labels with a nearest neighbors graph. In addition, an efficient accelerated proximal gradient(APG) algorithm is developed to solve the optimization problem. Finally, the experimental results on five benchmark image data sets for semi-supervised clustering and classification tasks demonstrate the superiority of this method over state-of-the-art methods.

Game Theoretical Approach for Non-Overlapping Community Detection

Graph clustering,i.e.,partitioning nodes or data points into non-overlapping clusters,can be beneficial in a large varieties of computer vision and machine learning applications.However,main graph clustering schemes,such as spectral clustering,cannot be applied to a large network due to prohibitive computational complexity required.While there exist methods applicable to large networks,these methods do not offer convincing comparisons against known ground truth.For the first time,this work conducts clustering algorithm performance evaluations on large networks(consisting of one million nodes)with ground truth information.Ideas and concepts from game theory are applied towards graph clustering to formulate a new proposed algorithm,Game Theoretical Approach for Clustering(GTAC).This theoretical framework is shown to be a generalization of both the Label Propagation and Louvain methods,offering an additional means of derivation and analysis.GTAC introduces a tuning parameter which allows variable algorithm performance in accordance with application needs.Experimentation shows that these GTAC algorithms offer scalability and tunability towards big data applications.