DISTRIBUTED K-CORE VIEW MATERIALIZATION AND MAINTENANCE FOR GRAPHS

摘要

Large graph data in many application domains dynamically changes with vertices and edges inserted and deleted over time. The problem of identifying and maintaining densely connected regions in the graph thus becomes a challenge. Embodiments of the invention describe a method using a k-core measure as a metric of dense connectivity over large, partitioned graph data stored in multiple computing servers in a cluster. The method describes steps to identify a k-core subgraph in parallel and to maintain a k-core subgraph when a new edge is inserted or an existing edge is deleted. The embodiments thus enable practitioners to identify and monitor large scale graph data, such as exemplified by multiple topical communities in a social network, in a scalable and efficient manner.

主权项

1. A computer implemented method associated with specified graph data comprising vertices and edges that each extends between two vertices, wherein the method comprises the steps of iteratively:
selecting each vertex from the specified graph data that has a degree which is equal to or greater than a given value k; determining whether a qualifying neighbor count (QNC) of each selected vertex is equal to or greater than k; deleting each edge incident at a vertex that has a QNC which is not equal to or greater than k; terminating the iterations when no more edges are deleted; and designating the remaining, undeleted graph data as a k-core subgraph.