TopPPR method for calculating large graph node proximity

A technology of proximity and nodes, which is applied in computing, computer components, instruments, etc., can solve problems such as inapplicability and inaccurate results returned by Top-kPPR, achieve good accuracy and running time, reduce time overhead, The effect of high computational efficiency

Pending Publication Date: 2018-11-09
RENMIN UNIVERSITY OF CHINA
View PDF0 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0006] Currently existing algorithms for solving the Top-k PPR query problem have two limitations
The first is that these methods have unacceptable space and time occupancy when applied to large images, or there is no precision guarantee for the returned results of Top-k PPR, which means that if you want accurate Top-k PPR As a result, some may be missed
Secondly, most algorithms require a preprocessing of directed graphs, which makes these methods unable to be applied to frequently updated graphs (such as social network graphs such as Twitter and Weibo)

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • TopPPR method for calculating large graph node proximity
  • TopPPR method for calculating large graph node proximity
  • TopPPR method for calculating large graph node proximity

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0049] The present invention will be described in detail below in conjunction with the accompanying drawings and embodiments.

[0050] The identifiers involved in the present invention and their meanings are shown in Table 1 below.

[0051] Table 1 Identifiers and their meanings

[0052]

[0053] The present invention first briefly introduces the basic definition of PPR and the definition of its accuracy.

[0054] PPR definition:

[0055] Let G=(V,E) represent a directed graph, V is the point set in the graph, the number of points is n, E is the edge set in the graph, the number of edges is m. Given a source point s ∈ V, an attenuation factor α, define a topological random walk starting from the source point s, each step of which either stops at the current point with the probability of α, or (1 -α) random walk to any neighbor node of the current point. Then for all points v∈V in the graph, the exact PPR value π(s,v) from s to v is equal to the probability of a random w...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention relates to a TopPPR method for calculating large graph node proximity. The method is characterized by including the following steps: 1) determining initial values of a Top-k node set anda candidate set; 2) performing forward search on the current candidate set and updating the current Top-k node set and the candidate set according to the forward search result; 3) on the basis of allnon-zero forward residual values obtained through forward search, executing nr times of random walk sampling and updating the current Top-k node set and the candidate set; 4) performing batch rearward search on the candidate set in step 3) and updating the current Top-k node set and the candidate set according to the rearward search result; 5) judging the number of nodes in the Top-k set, stopping iteration when a threshold condition is met, or repeating steps from step 2) to step 4) until the threshold condition is met, therefore, a final result is obtained. The method provided by the invention can be widely applied to a large graph node top-k inquiry field.

Description

technical field [0001] The invention relates to a method for calculating the proximity of large graph nodes, in particular to a TopPPR method for calculating the proximity of large graph nodes. Background technique [0002] PPR (Personalized PageRank) is a classic measure of the proximity of large graphs, which measures the degree of correlation between all nodes in a directed graph and a given node. In the related research on PPR, three types of PPR inquiries are mainly concerned: [0003] ① Point-to-point query: calculate the PPR value from the source point s to a fixed point v in the directed graph; [0004] ②Single-source query: calculate the PPR value from the source point s in the directed graph to all points in the graph; [0005] ③Top-k query: Find the point set corresponding to the largest k PPR values ​​starting from the source point s in the directed graph. Among the above types of queries, Top-k PPR queries are particularly important. [0006] Currently exist...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
IPC IPC(8): G06K9/62
CPCG06F18/22
Inventor 魏哲巍何晓东肖小奎王思博商烁文继荣
Owner RENMIN UNIVERSITY OF CHINA
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap