METHOD AND SYSTEM FOR DETECTING ANOMALIES IN A BIPARTITE GRAPH

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

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Ching-Yung, Tony, Hanghang
• Granted Patent: US 8,612,169 B2
• Time in Patent Office: Days
• US Class Current: 702/85
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

A method of detecting anomalies from a bipartite graph includes analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix, and in a processor, detecting the anomalies from the non-negative residual matrix.

Claims

1. A method of detecting anomalies from a bipartite graph, comprising:

analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix; and

in a processor, detecting the anomalies from the non-negative residual matrix.

2. The method of claim 1, wherein the anomalies comprise abnormal nodes and edges in the bipartite graph.

3. The method of claim 1, further comprising:

generating the graph from a data set,

wherein the analyzing comprises inferring the row-cluster membership, column-cluster membership and non-negative residual matrix from the graph.

4. The method of claim 3, wherein the detecting of anomalies comprises flagging abnormalities in the non-negative residual matrix.

5. The method of claim 1, wherein the bipartite graph comprises a people-activity graph and the anomalies comprise abnormal human behavior.

6. The method of claim 5, further comprising:

generating the people-activity graph from activity logs of a set of people,

wherein the analyzing comprises inferring people-community membership, community-activity membership and a non-negative people-activity residual matrix; and

wherein the detecting of anomalies comprises flagging the abnormal human behavior from the non-negative people-activity residual matrix.

7. The method of claim 6, wherein the inferring of the people-community membership, community-activity membership and a non-negative people-activity residual matrix comprises:

setting an initial people-community membership, an initial community-activity membership, and an initial non-negative people-activity residual matrix;

updating the initial people-community membership; and

updating the initial community-activity membership.

8. The method of claim 7, wherein the updating of the initial people-community membership comprises:

fixing and/or freezing the community-activity membership; and

re-calculating a strength of each person belonging to each community.

9. The method of claim 6, wherein the inferring of the people-community membership, community-activity membership and a non-negative people-activity residual matrix comprises:

setting an initial non-negative people-activity residual matrix;

inferring a rank-1 people-community membership and a rank-1 community-activity membership; and

updating the non-negative people-activity residual matrix.

10. The method of claim 9, wherein the inferring of the rank-1 people-community membership and the rank-1 community-activity membership comprises:

setting an initial rank-1 people-community membership, an initial rank-1 community-activity membership, and an initial non-negative people-activity residual matrix;

updating the initial rank-1 people-community membership; and

updating the initial rank-1 community-activity membership.

11. The method of claim 10, wherein the updating of the initial rank-1 people-community membership comprises:

fixing and/or freezing the rank-1 community-activity membership; and

re-calculating a strength of each person belonging to the community.

12. The method of claim 1, wherein the bipartite graph comprises an Internet Protocol (IP) source-destination graph and the anomalies comprise abnormal IP addresses.

13. The method of claim 12, further comprising:

generating an IP source-destination graph from IP trace logs,

wherein the analyzing comprises inferring an IP source-role membership, an IP destination-role membership and a non-negative IP source-destination residual matrix; and

wherein the detecting of anomalies comprises flagging abnormal IP addresses from the non-negative IP source-destination residual matrix.

14. A system for detecting anomalies from a bipartite graph, comprising:

an analyzer for analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix; and

a detector for detecting the anomalies from the non-negative residual matrix.

15. The system of claim 14, further comprising:

a graph generator for generating the graph from a data set,

wherein the analyzer infers the row-cluster membership, column-cluster membership and non-negative residual matrix from the graph, and

wherein the detector comprises a flagging device for flagging abnormalities in the non-negative residual matrix.

16. The system of claim 14, wherein the analyzer comprises:

an initial setting device for setting an initial row-cluster membership, an initial column-cluster membership, and an initial non-negative residual matrix;

an updater for updating the initial row-cluster membership; and

an updater for updating the initial column-cluster membership.

17. The system of claim 16, wherein the updater for updating the initial column-cluster membership comprises:

a fixing/freezing device for fixing and/or freezing the column-cluster membership; and

a strength re-calculator for re-calculating a strength of each member in the column-cluster membership.

18. The system of claim 14, wherein the analyzer comprises:

a setting device for setting an initial non-negative residual matrix; and

an updater for updating the initial non-negative residual matrix,

wherein the analyzer infers a rank-1 row-cluster membership and a rank-1 column-cluster membership by;

setting an initial rank-1 row-cluster membership, an initial rank-1 column-cluster membership, and an initial non-negative residual matrix;

updating the initial rank-1 row-cluster membership; and

updating the initial rank-1 column-cluster membership.

19. The system of claim 18, wherein the updater for updating the initial rank-1 row-cluster membership comprises:

a fixing/freezing device for fixing and/or freezing the rank-1 column-cluster membership; and

a strength re-calculator for re-calculating a strength of each member in the column-cluster membership.

20. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of detecting anomalies from a bipartite graph, the method comprising:

analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix; and

in a processor, detecting the anomalies from the non-negative residual matrix.