检索结果-内蒙古大学图书馆

label propagation algorithm for community discovery based on centrality and common neighbours

JOURNAL OF SUPERCOMPUTING 2024年第8期80卷 11816-11842页

作者： Douadi, Asma Kamel, Nadjet Sais, Lakhdar Univ Ferhat Abbas Setif 1 Dept Comp Sci LRSD Setif Algeria Univ Artois CRIL CNRS Lens France

We propose a label propagation-based algorithm to extract community structure using a new similarity measure based on centrality and common neighbours. Initially, a distinct label is assigned to each vertex. Along the process, each vertex adopts the label that most of its similar neighbours have. Communities are defined when closely related groups of vertices agree on a single label. Experiments on both real-world and synthetic networks show that our algorithm has better stability than the label propagation algorithm and finds communities with small sizes and indistinct boundaries more effectively than most state-of-the-art community detection methods.

关键词： label propagation algorithm Centrality Common neighbours Community structure

来源：评论

学校读者我要写书评

暂无评论

label propagation algorithm based on node similarity driven by local information

引用

INTERNATIONAL JOURNAL OF MODERN PHYSICS B 2019年第30期33卷

作者： Song, Chen Huang, Guoyan Yin, Bo Zhang, Bing Liu, Xinqian Yanshan Univ Coll Informat Sci & Engn 438 Hebei St Qinhuangdao 066004 Hebei Peoples R China 32153 Troops Chinese Peoples Liberat Army 56 Gebei St Zhangjiakou 075100 Hebei Peoples R China

label propagation algorithm (LPA) attracts wide attention in community detection field for its near linear time complexity in large scale network. However, the algorithm adopts a random selection scheme in label updating strategy, which results in unstable division and poor accuracy. In this paper, five different indicators of node similarity are introduced based on network local information to distinguish nodes and a new label updating method is proposed. When there are multiple maximum neighbor labels in the propagation process, the maximum label corresponding to the most similar node is selected for updating instead of a random one. Five different forms of improved LPA are proposed which are named as SAL-LPA, SOR-LPA, JAC-LPA, SOR-LPA, HDI-LPA and HPI-LPA. The experiment results on real-world and artificial benchmark networks show that the improved LPA greatly improves the performance of the original algorithm, among which HPI-LPA is the best.

关键词： Community detection complex network label propagation algorithm node similarity local information

来源：评论

学校读者我要写书评

暂无评论

Khmer Sentiment Lexicon Based on PU Learning and label propagation algorithm

引用

ACM TRANSACTIONS ON ASIAN AND LOW-RESOURCE LANGUAGE INFORMATION PROCESSING 2023年第3期22卷 1-18页

作者： Li, Chao Yan, Xin Xu, Guangyi Deng, Zhongying Mo, Yuanyuan Kunming Univ Sci & Technol Fac Informat Engn & Automat Kunming 650500 Yunnan Peoples R China

The sentiment lexicon is an important tool for natural language processing tasks. In addition to being able to determine the sentiment polarity of words or phrases, it can assist attribute-level, sentence-level, and text-level sentiment analysis tasks. In light of the fact that tagging data and corpora for the Khmer language are scarce, where most resources related to sentiment lexicons are for English, this paper proposes a method for constructing a sentiment lexicon for Khmer based on Positive-Unlabeled learning (PU Learning) and the label propagation algorithm. Sentiment words are first extracted from a corpus using the Spy technique of PU learning method. The main idea is to purify the set of N-class examples, train the MLP classifier, and continuously delete spy words and increase the number of P-class words in the iterative process. Following this, the sentiment polarity of the candidate words is determined. By considering the problem of determining the sentiment polarity of the candidate words as one of calculating its probability distribution, a small number of labeled sentiment words and candidate words are used to construct a graph model. The contextual information of the candidate words is used to construct a simple supplementary graphmodel of the set of sentiment words through word co-occurrence and triangulation, where this enhances the correlation between data items. The sentiment polarity of the candidate words is then determined through the label propagation algorithm. The results of experiments show that the proposed method can be used to construct a Khmer sentiment lexicon with a small number of labeled data and a small corpus without requiring excessive manual labeling.

关键词： Khmer sentiment lexicon PU learning label propagation algorithm graph model Spy technique

来源：评论

学校读者我要写书评

暂无评论

Graph-based label propagation algorithm for community detection

引用

INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS 2020年第6期11卷 1319-1329页

作者： Yang, Gui Zheng, Wenping Che, Chenhao Wang, Wenjian Shanxi Univ Sch Comp & Informat Technol Taiyuan 030006 Shanxi Peoples R China Minist Educ Key Lab Computat Intelligence & Chinese Informat Taiyuan 030006 Shanxi Peoples R China

Community detection is one of the most important topics in complex network analysis. Among a variety of approaches for detecting communities, the label propagation algorithm (LPA) is the simplest and time-efficient approach. However, the original label propagation algorithm is not stable due to the randomness in its propagation process. In this paper, we propose a graph-based label propagation algorithm (GLPA) to detect communities incorporating the node similarity and connectivity information during the propagation of the labels. First, we define node similarity between adjacent nodes, and change each node's label to that of its most similar neighbor node. Based on the label propagation process, GLPA constructs a label propagation graph to get candidate communities. Then, GLPA calculates the connected components of the label propagation graph. Each connected component is treated as a candidate community in the next step. Second, GLPA constructs a weighted graph to obtain final communities, in which each connected component are treated as a super-node, and the number of edges lying between the corresponding components as the weight of edges. We compute the merging factor for each node in the weighted graph and merge super nodes with higher merging factor to its most similar node iteratively to reach the maximum complementary entropy. Compared with 8 other classical community detection algorithms on LFR artificial networks and 12 real world networks, the proposed algorithm GLPA shows preferable performance on stability, NMI, ARI, modularity.

关键词： Complex network Community detection label propagation algorithm

来源：评论

学校读者我要写书评

暂无评论

Semantic community detection using label propagation algorithm

引用

JOURNAL OF INFORMATION SCIENCE 2016年第2期42卷 166-178页

作者： Kianian, Sahar Khayyambashi, Mohammad Reza Movahhedinia, Naser Univ Isfahan Fac Comp Engn Esfahan Iran

The issue of detecting large communities in online social networks is the subject of a wide range of studies in order to explore the network sub-structure. Most of the existing studies are concerned with network topology with no emphasis on active communities among the large online social networks and social portals, which are not based on network topology like forums. Here, new semantic community detection is proposed by focusing on user attributes instead of network topology. In the proposed approach, a network of user activities is established and weighted through semantic data. Furthermore, consistent extended label propagation algorithm is presented. Doing so, semantic representations of active communities are refined and labelled with user-generated tags that are available in web.2. The results show that the proposed semantic algorithm is able to significantly improve the modularity compared with three previously proposed algorithms.

关键词： Community detection label propagation algorithm semantic social network

来源：评论

学校读者我要写书评

暂无评论

Community detection using constrained label propagation algorithm with nodes exemption

引用

COMPUTING 2022年第2期104卷 339-358页

作者： Chin, Jia Hou Ratnavelu, Kuru UCSI Univ Fac Business & Management Kuala Lumpur 56000 Malaysia UCSI Univ Inst Comp Sci & Digital Innovat Kuala Lumpur 56000 Malaysia Univ Malaya Inst Math Sci Kuala Lumpur 50603 Malaysia

The detection of community structure plays an important role in understanding the properties and characteristics of complex networks. The label propagation algorithm (LPA) emerges as a popular community detection method, due to its simplicity and low computational cost. Nonetheless, the LPA is not without its limitations so that the Semi Synchronous Constrained label propagation algorithm (SSCLPA) is a modified LPA that implements various constraints to ameliorate the stability of the LPA. Aside from giving accurate and deterministic detection, it can avoid trivial detection. In this paper the SSCLPA is extended into weighted and directed networks, so that nodes which fulfill certain conditions are updated separately at the end of the algorithm. Furthermore, some modifications are performed on the propagation processes in the SSCLPA. These new features and modifications improve the time efficiency of the SSCLPA with only marginal loss in the quality of the detection. Our proposed method is tested and compared to the other community detection methods in various benchmark and real-world networks. The results showed that the proposed method is a well-balanced method with features that takes into account the stability, quality and time efficiency of the detection.

关键词： Complex networks Community structure Community detection label propagation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved label propagation algorithm-Based Method to Develop Sectionalizing Strategies for Parallel Power System Restoration

引用

IEEE ACCESS 2020年 8卷 118497-118509页

作者： Huang, Shujian Li, Changcheng Li, Zhicheng Xu, Wenwen Yang, Long Guangxi Univ Sch Elect Engn Nanning 530004 Peoples R China State Grid Fujian Elect Power Co Ltd Elect Power Res Inst Fuzhou 350007 Peoples R China

The first task of parallel power system restoration is to sectionalize the blackout system into multiple subsystems. This paper applies the complex network community discovery theory into this sectionalizing problem and proposes an improved label propagation algorithm-based sectionalizing method considering the system topology and operation before blackouts. Firstly, each blackstart (BS) unit bus is marked with a different subsystem label. A label propagation matrix is calculated based on the active power of branches before the blackout. Then, to avoid the label oscillation, a novel label impact strategy considering the influence of the bus label itself is developed to improve the label propagation matrix. The buses' labels propagate to neighboring buses as the improved label propagation matrix until they do not change. The initial sectionalizing strategy is obtained through classifying the buses with the same label in the same subsystem. Finally, the sectionalizing constraints are used to evaluate the feasibility of the initial strategy. For the initial strategy that does not satisfy the constraints, a refining method to minimize the absolute value of active power exchange among subsystems is proposed to determine the final sectionalizing strategy based on it. Case studies on IEEE 39-bus and IEEE 118-bus test systems verify the effectiveness of the proposed method. The results indicate that the proposed method has advantages in creating strongly connected subsystems.

关键词： Power system restoration sectionalizing strategy label propagation algorithm tie line

来源：评论

学校读者我要写书评

暂无评论

A spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networks

引用

DATA & KNOWLEDGE ENGINEERING 2018年 113卷 155-170页

作者： Sattari, Mohammad Zamanifar, Kamran Univ Isfahan Dept Comp Engn Esfahan Iran

Community detection in temporal social networks is an increasingly challenging subject in network analysis. The label propagation algorithm (LPA) is a simple and fast approach for community detection in dynamic networks. However, it tends to generate monster communities which decrease the accuracy of community detection, especially in dynamic social networks. In this paper, we propose a modified LPA, called Spreading Activation label propagation algorithm in order to solve the problem. This method assigns a property, called activation value, to each label, where pairs (label name, activation value) are propagated by spreading activation process and the LPA. Furthermore, this algorithm uses two weighting algorithms, where each of them corresponds to one variation of the proposed method. Here, the variations of the proposed method and other available methods on real and synthetic networks are implemented. Experimental results on both real and synthetic networks show that all variations of the proposed method detect communities more accurately compared to the benchmark methods while they are slower than these methods.

关键词： Spreading activation label propagation algorithm Overlapping community detection Dynamic social networks

来源：评论

学校读者我要写书评

暂无评论

New label propagation algorithm with pairwise constraints

引用

PATTERN RECOGNITION 2020年 106卷 107411-107411页

作者： Bai, Liang Wang, Junbin Liang, Jiye Du, Hangyuan Shanxi Univ Inst Intelligent Informat Proc Taiyuan 030006 Shanxi Peoples R China Shanxi Univ Sch Comp & Informat Technol Taiyuan 030006 Shanxi Peoples R China

The label propagation algorithm is a well-known semi-supervised clustering method, which uses pre-given partial labels as constraints to predict the labels of unlabeled data. However, the algorithm has the following limitations: (1) it does not fully consider the misalignment between the pre-given labels and clustering labels, and (2) it only uses label information as clustering constraints. Real applications not only contain partial label information but pairwise constraints on a dataset. To overcome these deficiencies, a new version of the label propagation algorithm is proposed, which makes use of pairwise relations of labels as constraints to construct an optimization model for spreading labels. Experimental analysis was used to compare the proposed algorithm with 8 other semi-supervised clustering algorithms on 11 benchmark datasets. The experimental results demonstrated that the proposed algorithm is more effective than other algorithms. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Cluster analysis Semi-supervised clustering label propagation algorithm Pairwise constraint Spectral clustering

来源：评论

学校读者我要写书评

暂无评论

An improved label propagation algorithm based on node importance and random walk for community detection

引用

MODERN PHYSICS LETTERS B 2017年第14期31卷

作者： Ma, Tianren Xia, Zhengyou Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210015 Jiangsu Peoples R China

Currently, with the rapid development of information technology, the electronic media for social communication is becoming more and more popular. Discovery of communities is a very effective way to understand the properties of complex networks. However, traditional community detection algorithms consider the structural characteristics of a social organization only, with more information about nodes and edges wasted. In the meanwhile, these algorithms do not consider each node on its merits. label propagation algorithm (LPA) is a near linear time algorithm which aims to find the community in the network. It attracts many scholars owing to its high efficiency. In recent years, there are more improved algorithms that were put forward based on LPA. In this paper, an improved LPA based on random walk and node importance (NILPA) is proposed. Firstly, a list of node importance is obtained through calculation. The nodes in the network are sorted in descending order of importance. On the basis of random walk, a matrix is constructed to measure the similarity of nodes and it avoids the random choice in the LPA. Secondly, a new metric IAS (importance and similarity) is calculated by node importance and similarity matrix, which we can use to avoid the random selection in the original LPA and improve the algorithm stability. Finally, a test in real-world and synthetic networks is given. The result shows that this algorithm has better performance than existing methods in finding community structure. \

关键词： Community detection label propagation algorithm random walk node importance

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：