Community detection is a vital task in many fields,such as social networks and financial analysis,to name a few.The Louvain method,the main workhorse of community detection,is a popular heuristic method.To apply it to...Community detection is a vital task in many fields,such as social networks and financial analysis,to name a few.The Louvain method,the main workhorse of community detection,is a popular heuristic method.To apply it to large-scale graph networks,researchers have proposed several parallel Louvain methods(PLMs),which suffer from two challenges:the latency in the information synchronization,and the community swap.To tackle these two challenges,we propose an isolate sets based parallel Louvain method(IPLM)and a fusion IPLM with the hashtables based Louvain method(FIPLM),which are based on a novel graph partition algorithm.Our graph partition algorithm divides the graph network into subgraphs called isolate sets,in which the vertices are relatively decoupled from others.We first describe the concepts and properties of the isolate set.Second we propose an algorithm to divide the graph network into isolate sets,which enjoys the same computation complexity as the breadth-first search.Third,we propose IPLM,which can efficiently calculate and update vertices information in parallel without latency or community swap.Finally,we achieve further acceleration by FIPLM,which maintains a high quality of community detection with a faster speedup than IPLM.Our two methods are for shared-memory architecture,and we implement our methods on an 8-core PC;the experiments show that IPLM achieves a maximum speedup of 4.62x and outputs higher modularity(maximum 4.76%)than the serial Louvain method on 14 of 18 datasets.Moreover,FIPLM achieves a maximum speedup of 7.26x.展开更多
由于社会网络分析可以反映决策者在大群体决策(large group decision making,LGDM)共识问题中的社会关系,因此研究基于社会网络的LGDM共识问题具有现实意义。本文通过考虑决策者之间的社会网络关系,提出了一种交互式共识模型:首先,根据...由于社会网络分析可以反映决策者在大群体决策(large group decision making,LGDM)共识问题中的社会关系,因此研究基于社会网络的LGDM共识问题具有现实意义。本文通过考虑决策者之间的社会网络关系,提出了一种交互式共识模型:首先,根据决策者之间的社会关系,采用Louvain方法对网络进行聚类,以降低大规模社会网络的复杂性;然后,基于可能性分布的犹豫模糊元素来表示每个子群的偏好,根据社会网络分析的中心性,计算决策者和子群权重;随后,给出三个层次的共识测量和反馈机制,来加速共识的达成过程。该模型在一致性调整过程中,整个社会网络也随之更新,允许子群分类的改变,而且考虑决策者的交互使结果更容易被接受。最后,通过案例分析验证方法的可行性,并通过与现有方法的比较,说明了方法的优越性。展开更多
基金supported by the Key Program of National Natural Science Foundation of China under Grant No.61732018the National Natural Science Foundation of China under Grant No.61902415the Open Foundation of Science and Technology on Parallel and Distributed Laboratory(School of Computer,National University of Defense Technology)under Grant No.6142110190201.
文摘Community detection is a vital task in many fields,such as social networks and financial analysis,to name a few.The Louvain method,the main workhorse of community detection,is a popular heuristic method.To apply it to large-scale graph networks,researchers have proposed several parallel Louvain methods(PLMs),which suffer from two challenges:the latency in the information synchronization,and the community swap.To tackle these two challenges,we propose an isolate sets based parallel Louvain method(IPLM)and a fusion IPLM with the hashtables based Louvain method(FIPLM),which are based on a novel graph partition algorithm.Our graph partition algorithm divides the graph network into subgraphs called isolate sets,in which the vertices are relatively decoupled from others.We first describe the concepts and properties of the isolate set.Second we propose an algorithm to divide the graph network into isolate sets,which enjoys the same computation complexity as the breadth-first search.Third,we propose IPLM,which can efficiently calculate and update vertices information in parallel without latency or community swap.Finally,we achieve further acceleration by FIPLM,which maintains a high quality of community detection with a faster speedup than IPLM.Our two methods are for shared-memory architecture,and we implement our methods on an 8-core PC;the experiments show that IPLM achieves a maximum speedup of 4.62x and outputs higher modularity(maximum 4.76%)than the serial Louvain method on 14 of 18 datasets.Moreover,FIPLM achieves a maximum speedup of 7.26x.
文摘由于社会网络分析可以反映决策者在大群体决策(large group decision making,LGDM)共识问题中的社会关系,因此研究基于社会网络的LGDM共识问题具有现实意义。本文通过考虑决策者之间的社会网络关系,提出了一种交互式共识模型:首先,根据决策者之间的社会关系,采用Louvain方法对网络进行聚类,以降低大规模社会网络的复杂性;然后,基于可能性分布的犹豫模糊元素来表示每个子群的偏好,根据社会网络分析的中心性,计算决策者和子群权重;随后,给出三个层次的共识测量和反馈机制,来加速共识的达成过程。该模型在一致性调整过程中,整个社会网络也随之更新,允许子群分类的改变,而且考虑决策者的交互使结果更容易被接受。最后,通过案例分析验证方法的可行性,并通过与现有方法的比较,说明了方法的优越性。
