Single-round kernel value maintenance method for multilateral updating under dynamic graph

A dynamic graph and core value technology, applied in the direction of instruments, relational databases, database models, etc., can solve the problem of high time overhead, achieve the effects of improving calculation speed, good scalability and stability, and reducing time overhead

Active Publication Date: 2019-09-10
HUAZHONG UNIV OF SCI & TECH
View PDF5 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0006] The present invention provides a single-round core value maintenance method for multilateral update under dynamic graphs, which is used to solve the technical problem of excessive time overhead due to the need for multiple algorithm iterations in the existing dynamic graph core value maintenance process

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
  • Single-round kernel value maintenance method for multilateral updating under dynamic graph
  • Single-round kernel value maintenance method for multilateral updating under dynamic graph
  • Single-round kernel value maintenance method for multilateral updating under dynamic graph

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0053] A single-round core value maintenance method for multi-edge update under a dynamic graph. When inserting a point or an edge under a dynamic graph of a social network, the vertex core value maintenance sub-method 100 is adopted when inserting a point or an edge under a dynamic graph, such as figure 1 As shown, the vertex core value maintenance sub-method includes:

[0054] Step 110, determine the candidate degree, core value and stay degree of each vertex in the current dynamic graph, and classify each vertex to form a plurality of k-order sets. k , k is the O k The current kernel value of each vertex in

[0055] Step 120, based on all points or edges to be inserted, update the candidate degree of each vertex;

[0056] Step 130, according to the order of k from small to large, determine an O k , based on the O k According to the candidate degree and stay degree of a vertex v, judge whether the vertex v is a core value increase point;

[0057] Step 140, if yes, updat...

Embodiment 2

[0105] A single-round core value maintenance method for multi-edge update under a dynamic graph. When deleting a point or an edge under a dynamic graph of a social network, the vertex core value maintenance sub-method 200 is adopted when a point or an edge is deleted under a dynamic graph, such as Figure 5 As shown, the vertex core value maintenance sub-method includes:

[0106] Step 210, determine the superiority number and kernel value of each vertex in the current dynamic graph;

[0107] Step 220, based on all vertices or edges to be deleted, update the degree of excellence of each vertex;

[0108] Step 230, each vertex whose goodness number is smaller than its kernel value is determined as a kernel value reduction point;

[0109] Step 240, based on the kernel value of each kernel value reduction point, determine other missing kernel value reduction points from all vertices;

[0110] Step 250 , update the kernel value and goodness of each kernel value reduction point, an...

Embodiment 3

[0134] A storage medium, in which instructions are stored, and when the computer reads the instructions, the computer is made to execute any sub-method for maintaining vertex core values ​​when inserting points or edges under a dynamic graph as described in Embodiment 1 And / or any sub-method for maintaining vertex core values ​​when deleting points or edges under the dynamic graph as described in the second embodiment.

[0135] The relevant technical solutions are the same as those in Embodiment 1 and Embodiment 2, and will not be repeated here.

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 discloses a single-round kernel value maintenance method for multilateral updating under a dynamic graph. The method comprises a vertex kernel value maintenance single-round algorithm when a point or an edge is inserted and a vertex kernel value maintenance single-round algorithm when the point or the edge is deleted. Before updating the graph, a globally ordered node order is maintained. All edges are added into a single round by an insert point or edge kernel value maintenance algorithm at a time, then the vertexes are traversed in sequence, and the influence of the vertexes with the increased kernel values is moved to the vertexes with the high order until the kernel values of the vertexes are not changed. All the edges in a single round are deleted by using the kernel value maintenance algorithm of the deletion point or edge, traversal is started from the vertexes of the deleted edges, and the continuous iteration is carried out until the kernel values of all the vertexes are in a stable state. According to the method, the kernel value maintenance of all vertexes is completed through the single round of algorithm, the redundant calculation on the vertexes during the graph traversing process is reduced, the kernel value maintenance time is shortened, and the method has the extremely good expansibility and stability especially for the large-scale graphs.

Description

technical field [0001] The invention belongs to the technical field of social network graph data mining, and in particular relates to a single-round kernel value maintenance method for multilateral updating under dynamic graphs. Background technique [0002] The graph data structure can well express the correlation between data. Many practical problems can be abstracted as a graph data structure, where each individual instance is abstracted as a vertex in the graph, and the relationship between each entity is abstracted as an edge between two vertices. Many big data problems exist in the form of large-scale graphs or networks, such as social networks, transportation network graphs, infectious disease transmission path analysis graphs, and dependency graphs in academic papers. [0003] However, with the vigorous development of the Internet, the scale of the graph is increasing exponentially, and the relationship between the vertices in the graph is becoming more and more com...

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
Patent Type & Authority Applications(China)
IPC IPC(8): G06F16/22G06F16/2458G06F16/28
CPCG06F16/2237G06F16/2465G06F16/288
Inventor 华强胜金海史瑜良于东晓
Owner HUAZHONG UNIV OF SCI & TECH
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