DETERMINING THE IMPORTANCE OF DATA ITEMS AND THEIR CHARACTERISTICS USING CENTRALITY MEASURES

• US 20120278261A1
• Filed: 04/28/2011
• Published: 11/01/2012
• Est. Priority Date: 04/28/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Ching-Yung, Sun, Jimeng, Papadimitriou, Spyridon, Tong, Hanghang, Kang, U
• Granted Patent: US 8,818,918 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

Computer-implemented methods, systems, and articles of manufacture for determining the importance of a data item. A method includes: (a) receiving a node graph; (b) approximating a number of neighbor nodes of a node; and (c) calculating a average shortest path length of the node to the remaining nodes using the approximation step, where this calculation demonstrates the importance of a data item represented by the node. Another method includes: (a) receiving a node graph; (b) building a decomposed line graph of the node graph; (c) calculating stationary probabilities of incident edges of a node graph node in the decomposed line graph, and (d) calculating a summation of the stationary probabilities of the incident edges associated with the node, where the summation demonstrates the importance of a data item represented by the node. Both methods have at least one step carried out using a computer device.

Claims

1. ) A computer implemented method for determining the importance of a data item in an electronic network, said method comprising the steps of:

receiving a node graph,

wherein said node graph is a representation of at least two data items with at least one relationship between said at least two data items,

wherein said at least two data items are represented by nodes on said node graph, and

wherein said at least one relationship is represented by at least one edge between said nodes;

approximating a number of neighbor nodes of at least one node of said node graph; and

calculating a average shortest path length from said at least one node to remaining nodes contained in said node graph using said approximated number of neighbor nodes, wherein said calculated average shortest path demonstrates the importance of a data item represented by said at least one node,

wherein at least one step is carried out using a computer device.

2. ) The method according to claim 1 wherein said approximation step is performed by an estimation algorithm that iteratively updates a sum representing a total number of neighbor nodes, and wherein said iteration begins with a minimum defined unit and ends when said iteration reaches a value equivalent to a diameter of said node graph.

3. ) The method according to claim 2 wherein said estimation algorithm is a Flajolet-Martin algorithm.

4. ) The method according to claim 3 wherein bit-strings of said Flajolet-Martin algorithm are iteratively updated by a bitwise-or operation.

5. ) The method according to claim 4 wherein the steps of the method are performed for multiple nodes in said node graph, wherein said multiple nodes are connected by edges representing said at least one relationship.

6. ) The method according to claim 5, wherein said multiple nodes comprise labeled nodes and unlabeled nodes, and wherein the method comprises the additional steps of:

receiving labels associated with said labeled nodes of said node graph, wherein said labels are based on said at least one relationship;

training a classifier that associates a label of a labeled node with a average shortest path length of said labeled node; and

applying said classifier to a unlabeled node, wherein said classifier labels said unlabeled node based on said association by using a average shortest path length of said unlabeled node.

7. ) The method according to claim 5, wherein said multiple nodes represent multiple data items containing an anomaly, and wherein the method comprises the additional steps of:

detecting an anomaly contained in said multiple data items containing an anomaly; and

flagging a source of said anomaly in said multiple data items containing an anomaly by using said calculating step, wherein a anomalous data item with a corresponding node in said node graph with a smallest average shortest path length operates as said source of said anomaly.

8. ) The method according to claim 5 comprising the additional steps of:

ranking each node of said multiple nodes by a score determined by using said calculating step, wherein said score of a ranked node increases as the average shortest path length of said ranked node decreases;

outputting a ranked node with a highest score;

calculating at least one additional characteristic associated with each ranked node; and

displaying a relationship between said additional characteristic for said each ranked node and said score for said each ranked node.

9. ) The method according to claim 5 wherein said multiple nodes represent data items that are email data items of individuals in an organization, and wherein said at least one relationship represents email exchanges between said email data items, and the method comprises the additional step of:

identifying importance of an individual within said organization using said calculating step, wherein said importance increases as said average shortest path length of a node representing an email data item of said individual decreases.

20. ) An article of manufacture comprising a computer readable storage medium having computer readable instructions embodied therein that, when executed by a computer, implements the method according to claim 1.

10. ) A computer implemented method for determining the importance of a data item in an electronic network, said method comprising the steps of:

receiving a node graph,

wherein said node graph is a representation of at least two data items with at least one relationship between said at least two data items,

wherein said at least two data items are represented by nodes on said node graph, and

wherein said at least one relationship is represented by at least one edge between said nodes;

building an approximation of a line graph of said node graph by decomposing said line graph into sparse matrixes;

calculating stationary probabilities of edges in said decomposed line graph using said sparse matrixes, wherein said edges are incident edges associated with at least one node of said node graph; and

calculating a summation of said stationary probabilities of said incident edges associated with said at least one node of said node graph, wherein said summation demonstrates the importance of a data item represented by said at least one node,

wherein at least one step is carried out using a computer device.

11. ) The method according to claim 10 wherein said at least one edge carries a weighted value, and wherein said line graph is a weighted line graph.

12. ) The method according to claim 11 wherein said calculating stationary probabilities steps uses a Page Rank algorithm on said decomposed weighted line graph.

13. ) The method according to claim 12 comprising the additional step of:

building a normalization factor prior to performing said calculating steps, wherein said normalization factor is used to make said sparse matrices suitable for power iteration, and wherein said Page Rank algorithm is performed by power iteration.

14. ) The method according to claim 13 wherein the steps of the method are performed for multiple nodes of said node graph, and wherein said multiple nodes are connected by edges representing said at least one relationship.

15. ) The method according to claim 14, wherein said multiple nodes comprise labeled nodes and unlabeled nodes, and wherein the method comprises the additional steps of:

receiving labels associated with said labeled nodes of said node graph, wherein said labels are based on said at least one relationship;

training a classifier that associates a label of a labeled node with a summation of said stationary probabilities of said labeled node; and

applying said classifier to a unlabeled node, wherein said classifier labels a unlabeled node based on said association by using a summation of said stationary probabilities of said unlabeled node.

16. ) The method according to claim 14, wherein said multiple nodes represent multiple data items containing an anomaly, and wherein the method comprises the additional steps of:

detecting an anomaly contained in said multiple data items containing an anomaly; and

flagging a source of said anomaly in said multiple data items containing an anomaly by using said calculating a summation step, wherein a anomalous data item with a corresponding node in said node graph with a highest value of said summation of stationary probabilities operates as said source of said abnormality.

17. ) The method according to claim 14 comprising the additional steps of:

ranking each node of said multiple nodes by a score determined by using said calculating a summation step, wherein said score of a ranked node increases as the summation of stationary probabilities value increases for said ranked node.

outputting a ranked node with a highest score;

calculating at least one additional characteristic associated with each ranked node of said node graph; and

displaying a relationship between said additional characteristic for said each ranked node and said score for said each ranked node.

21. ) An article of manufacture comprising a computer readable storage medium having computer readable instructions embodied therein that, when executed by a computer, implements the method according to claim 10.

18. ) A computer implemented data assessment system for determining the importance of a data item, said system comprising:

an input receiving unit configured to receive a node graph,

wherein said node graph is a representation of at least two data items with at least one relationship between said at least two data items,

wherein said at least two data items are represented by nodes on said node graph,

wherein said at least one relationship is represented by at least one edge between said nodes;

an approximating unit configured to approximate a number of neighbor nodes of at least one node of said node graph; and

a calculating unit configured to calculate a average shortest path length from said at least one node to remaining nodes contained in said node graph using said approximated number of neighbor nodes, wherein said calculated average shortest path demonstrates the importance of a data item represented by said at least one node.

19. ) A computer implemented data assessment system for determining the importance of a data item, said system comprising:

an input receiving unit configured to receive a node graph,

wherein said node graph is a representation of at least two data items with at least one relationship between said at least two data items,

wherein said at least two data items are represented by nodes on said node graph,

wherein said at least one relationship is represented by at least one edge between said nodes;

a building unit configured to build an approximation of a line graph of said node graph by decomposing said line graph into sparse matrixes;

a calculating a stationary probability unit configured to compute stationary probabilities of edges in said decomposed line graph using said sparse matrices, wherein said edges are incident edges associated with at least one node of said node graph; and

a calculating a summation unit configured to compute a summation of said stationary probabilities of said incident edges associated with said at least one node of said node graph, wherein said summation demonstrates the importance of a data item represented by said at least one node.