Back to results
US 7,890,510 B2Granted
Method and apparatus for analyzing community evolution in graph data streams
AssigneeInternational Business Machines Corporation
InventorsCharu C. Aggarwal, Philip Shi-Lung Yu
Life of this patent
Estimating the term…
Abstract
Improved techniques are disclosed for detecting patterns of interaction among a set of entities and analyzing community evolution in a stream environment. By way of example, a technique for processing data from a data stream includes the following steps/operations. A data point of the data stream representing an interaction event is obtained. An interaction graph is updated on-line based on the data point representing the interaction event. The updated interaction graph is stored in a nonvolatile memory. An interaction evolution is determined off-line from the updated interaction graph stored in the nonvolatile memory.
Claims21
A method for processing data from a data stream, comprising the steps of:
- obtaining a data point of the data stream, the data point representing an interaction event;
- updating on-line an interaction graph based on the data point representing the interaction event associated with the obtained data point of the data stream, wherein the interaction graph represents an interaction model wherein nodes in the interaction graph represent entities and edges in the interaction graph represent interactions between the entities, and the interaction event associated with the obtained data point of the data stream is modeled by a pair of elements comprising a first element corresponding to an edge associated with two entities between whom the interaction event has taken place and a second element corresponding to a weight of the edge that is associated with the interaction which has taken place between the two entities;
- storing the updated interaction graph in a nonvolatile memory;
- and
- determining off-line an interaction evolution from the updated interaction graph stored in the nonvolatile memory, wherein the off-line determination of the interaction evolution further comprises:
- normalizing the updated interaction graph and another time instance of the interaction graph stored in the nonvolatile memory;
- forming a differential graph by subtracting the normalized updated interaction graph from the normalized another time instance of the interaction graph;
- constructing clusters by assigning nodes to seed nodes, wherein the seed nodes and the assigned nodes of the clusters are selected from the differential graph;
- and
- computing a bias for each cluster using a function of a fraction of positive weight edges in the respective cluster;
- wherein the bias of each of the clusters is indicative of interaction expansion, interaction contraction or interaction stability.
8 more elements
An apparatus for processing data from a data stream, comprising:
- a main memory;
- and
- at least one processor coupled to the main memory and operative to:
- (i) obtain a data point of the data stream, the data point representing an interaction event;
- (ii) update on-line an interaction graph based on the data point representing the interaction event associated with the obtained data point of the data stream, wherein the interaction graph represents an interaction model wherein nodes in the interaction graph represent entities and edges in the interaction graph represent interactions between the entities, and the interaction event associated with the obtained data point of the data stream is modeled by a pair of elements comprising a first element corresponding to an edge associated with two entities between whom the interaction event has taken place and a second element corresponding to a weight of the edge that is associated with the interaction which has taken place between the two entities;
- (iii) store the updated interaction graph in a nonvolatile memory;
- and
- (iv) determine off-line an interaction evolution from the updated interaction graph stored in the nonvolatile memory, wherein the off-line determination of the interaction evolution further comprises:
- normalizing the updated interaction graph and another time instance of the interaction graph stored in the nonvolatile memory;
- forming a differential graph by subtracting the normalized updated interaction graph from the normalized another time instance of the interaction graph;
- constructing clusters by assigning nodes to seed nodes, wherein the seed nodes and assigned nodes of the clusters are selected from the differential graph;
- and
- computing a bias for each cluster using a function of a fraction of positive weight edges in the respective cluster;
- wherein the bias of each of the clusters is indicative of interaction expansion, interaction contraction or interaction stability.
11 more elements
An article of manufacture for use in processing data from a data stream, the article comprising a processor readable storage medium containing one or more programs which when executed implement the steps of:
- obtaining a data point of the data stream, the data point representing an interaction event;
- updating on-line an interaction graph based on the data point representing the interaction event associated with the obtained data point of the data stream, wherein the interaction graph represents an interaction model wherein nodes in the interaction graph represent entities and edges in the interaction graph represent interactions between the entities, and the interaction event associated with the obtained data point of the data stream is modeled by a pair of elements comprising a first element corresponding to an edge associated with two entities between whom the interaction event has taken place and a second element corresponding to a weight of the edge that is associated with the interaction which has taken place between the two entities;
- storing the updated interaction graph in a nonvolatile memory;
- and
- determining off-line an interaction evolution from the updated interaction graph stored in the nonvolatile memory, wherein the off-line determination of the interaction evolution further comprises:
- normalizing the updated interaction graph and another time instance of the interaction graph stored in the nonvolatile memory;
- forming a differential graph by subtracting the normalized updated interaction graph from the normalized another time instance of the interaction graph;
- constructing clusters by assigning nodes to seed nodes, wherein the seed nodes and assigned nodes of the clusters are selected from the differential graph and;
- computing a bias for each cluster using a function of a fraction of positive weight edges in the respective cluster;
- wherein the bias of each of the clusters is indicative of interaction expansion, interaction contraction or interaction stability.
7 more elements
Dependencies are inferred from the claim text.