Title:
UNCERTAIN GRAPH-BASED COMMUNITY DISCOVERY METHOD
Document Type and Number:
WIPO Patent Application WO/2022/056955
Kind Code:
A1
Abstract:
Disclosed in the present invention is an uncertainty graph-based community discovery method. Said method comprises the following steps: step 1, acquiring uncertain data in an actual network, constructing an uncertain graph, and storing the uncertain graph in the form of an adjacency linked list; step 2, using a stable structural clustering algorithm to mine stable core nodes, hub nodes, and outlier nodes in the uncertain graph, and constructing stable structure clusters from the stable core nodes; and step 3, constructing a community from the stable structure clusters, i.e. the community structure in the uncertain graph. The method disclosed in the present invention takes account of both the reliability of edges and the reliability of core nodes in an uncertain graph, so that in the finally obtained community, stable core nodes and reliable edges connecting the stable core nodes in the community both can satisfy certain reliability requirements; and in the present invention, an efficient stable structure clustering algorithm is used to calculate stable core nodes in an uncertain graph, and on this basis, a community structure is mined, so that the calculation complexity is low, being able to be applied to large-scale graph data.
Inventors:
YU DONGXIAO (CN)
LI FENG (CN)
WANG DONGBIAO (CN)
LUO QI (CN)
LI FENG (CN)
WANG DONGBIAO (CN)
LUO QI (CN)
Application Number:
PCT/CN2020/118130
Publication Date:
March 24, 2022
Filing Date:
September 27, 2020
Export Citation:
Assignee:
UNIV SHANDONG (CN)
International Classes:
G06F16/901
Foreign References:
| CN104573730A | 2015-04-29 | |||
| CN106980795A | 2017-07-25 | |||
| US20140149430A1 | 2014-05-29 |
Other References:
"Master's Thesis of Shenzhen University", 15 July 2019, SHENZHEN UNIVERSITY, CN, article QIU YUXUAN: "Research and Implementation of Structural Clustering on Probabilistic Graphs", XP055913809
Attorney, Agent or Firm:
QINGDAO ARTFIX PATENT AGENCY (GENERAL PARTNERSHIP) (CN)
Download PDF: