Social network aware pattern detection

• US 7,856,411 B2
• Filed: 02/12/2007
• Issued: 12/21/2010
• Est. Priority Date: 03/21/2006
• Status: Active Grant

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: 21st Century Technologies, Inc.
• Inventors: Darr, Timothy Paul
• Primary Examiner(s): HOLMES, MICHAEL B
• Application Number:
  US11/673,816
• Publication Number:
  US 20070226248A1
• Time in Patent Office: 1,408 Days
• Field of Search: 706/45
• US Class Current: 706/45
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Enabling dynamic, computer-driven, context-based detection of social network patterns within an input graph representing a social network. A Social Network Aware Pattern Detection (SNAP) system and method utilizes a highly-scalable, computationally efficient integration of social network analysis (SNA) and graph pattern matching. Social network interaction data is provided as an input graph having nodes and edges. The graph illustrates the connections and/or interactions between people, objects, events, and activities, and matches the interactions to a context. A sample graph pattern of interest is identified and/or defined by the user of the application. With this sample graph pattern and the input graph, a computational analysis is completed to (1) determine when a match of the sample graph pattern is found, and more importantly, (2) assign a weight (or score) to the particular match, according to a pre-defined criteria or context.

Claims

1. A method comprising:

initiating graph pattern matching within an input graph that represents a social network, said graph pattern matching utilizing pre-defined social network analysis (SNA) metrics to provide a context for finding a true match, wherein the graph pattern matching locates one or more matched graphs within the input graph having similar inter-connections among nodes as a target graph pattern; and

analyzing each matched graph using SNA metrics-based context from at least one of local node attributes within the matched graph and non-local node attributes, external to the matched graph, to determine when the matched graph is a true match.

2. The method of claim 1, wherein the analyzing further comprises:

assigning a weight to each matched graph based on a defined context, which defined context takes into consideration an inter-connection of the matched graph to one or more external nodes of interest within the larger input graph, wherein said weight indicates a relative importance of the matched graph within the defined context;

comparing the weight of each matched pattern against a pre-established threshold weight;

marking only matched patterns with a weight above the pre-established threshold weight as true matches, which may be relevant for further analysis; and

when an output/alert feature is provided within the graph pattern matching, generating an output/alert which identifies the matched patterns that are true matches.

3. The method of claim 1, further comprising:

calculating a score for each matched graph identified;

ranking the score of each matched graph against a pre-established scale for ranking matched graphs; and

outputting a set of resulting matched graphs in order of said ranking using one of a first output scheme, a second output scheme, and a third output scheme, wherein the first output schemes places a higher ranked match graph ahead of a lower ranked matched graph, the second output scheme outputs the matched graphs in reverse order to the first output scheme, and the third output scheme outputs only those matched graphs whose score is above a pre-established minimum score.

4. The method of claim 1, further comprising:

identifying a node of interest within the input graph, wherein the node of interest is one of a singular node or a node within a group of interconnected nodes, and wherein said node of interest is inter-connected to other nodes within the social network via one or more interconnection means;

establishing a maximum path length as a first SNA metric that defines the context, wherein said path length represents a number of hops separating the node of interest from a specified node within a matched graph;

determining an actual path length between the node of interest and the specified node within each matched graph identified; and

selecting each matched graph whose path length is not greater than the maximum path length as a true match, wherein matched patterns whose path lengths are greater than the maximum path length are determined to be out-of-context matched graphs that were false positives.

5. The method of claim 4, further comprising:

searching only within the maximum path length of the node of interest to find the specified node;

wherein the path length SNA metric is utilized to curtail and filter the matches of the target pattern graph to substantially reduce a number of false positives of matched graphs, which are located outside the path length within the input graph.

6. The method of claim 1, further comprising:

identifying an intermediary node that may be neutralized to remove a connection between a first matched pattern and the node of interest, wherein the intermediary node bridges communication between a group represented by the first matched pattern and the node of interest.

7. The method of claim 1, wherein said context comprises one or more SNA metrics including:

SNA metric intervals, which provides at least one of a maximum range and a minimum range from a specified node within which to constrain and focus a search for the matched graphs;

average cycle length;

average path length;

centrality measures;

circumference;

clique measures;

clustering measures;

degree;

density;

diameter;

girth;

number of nodes;

radius; and

radiality.

8. The method of claim 1, further comprising:

defining an SNA metric of interest along with a pre-established tracking parameter, such as a threshold;

tracking the SNA metric at each step of completing the graph pattern matching; and

automatically terminating the graph pattern matching when a value of the pre-established tracking parameter exceeds a pre-set threshold for the SNA metric.

9. The method of claim 1, farther comprising:

providing a range within which a particular SNA metric falls, said range comprising a lower-bound and an upper-bound;

when the range represents an exclusion range, automatically terminating the graph pattern matching when the value for the particular SNA metric falls within the pre-established interval; and

when the range represents an inclusion range, automatically terminating the graph pattern matching when the value for the particular SNA metric falls outside the pre-established interval.

10. The method of claim 1, wherein initiating graph pattern matching further comprises:

integrating pre-defined SNA constructs, including groups, into the graph pattern matching, wherein, group membership is accounted for when utilizing SNA metrics to define the match criteria, wherein a match predicate is defined that requires a matched node be a member of a group with certain characteristics;

defining an SNA group that comprises one or more nodes having pre-defined inter-connection characteristics; and

completing the graph pattern matching utilizing the SNA groups as one component of the context.

11. The method of claim 1, further comprising one or more of:

defining a particular social role within the social network as a gatekeeper, based on a connection of person, events and activities to a node representing the gatekeeper; and

defining roles for particular nodes within the input graph, including;

a first role, which represents a known entity exhibiting certain known characteristics/tendencies and intentions;

a second role, which represents an entity that has some kind of association with a target node; and

a third role, which represents a next entity that is connected to entities representing both the first role and the second role.

12. The method of claim 11, further comprising:

matching nodes against certain SNA roles and positions when completing the graph matching, wherein the nodes include nodes representing entities with high centrality measures, communication gateways, cut-outs, and reach-ability to other particular entities of interest; and

analyzing a node within the input graph against a select node within a target pattern graph using the pre-determined SNA metric to determine if the node in the input graph matches the select node in the target pattern graph.

13. The method of claim 1, further comprising:

performing an activity scoring of the matched pattern using SNA metric inputs, wherein said activity scoring increases or decreases an activity score of the matched pattern, said activity score indicating whether a matched pattern is a pattern of interest; and

when the activity is identified within the input graph;

increasing the activity score when the SNA metric is utilized as an additional qualifier for an activity desired to have a higher activity score; and

decreasing the activity score when the SNA metric is utilized as an additional qualifier for an activity desired to have a lower activity score.

14. The method of claim 1, further comprising:

determining a degree of centrality of a particular node using a centrality measure;

comparing the degree of centrality against a pre-established threshold value;

tagging the node as a node of interest when the degree of centrality of the particular node is above the pre-established threshold.

15. A computer program product comprising:

a non-transitory computer readable medium; and

program code on the non-transitory computer readable medium that when executed provides the functions of;

initiating graph pattern matching within an input graph that represents a social network, said graph pattern matching utilizing pre-defined social network analysis (SNA) metrics to provide a context for finding a true match, wherein the graph pattern matching locates one or more matched graphs within the input graph having similar inter-connections among nodes as a target graph pattern; and

analyzing each matched graph using SNA metrics-based context from at least one of local node attributes within the matched graph and non-local node attributes, external to the matched graph, to determine when the matched graph is a true match.

16. The computer program product of claim 15, wherein the program instructions for analyzing further comprises program instructions for:

assigning a weight to each matched graph based on a defined context, which defined context takes into consideration an inter-connection of the matched graph to one or more external nodes of interest within the larger input graph, wherein said weight indicates a relative importance of the matched graph within the defined context;

comparing the weight of each matched pattern against a pre-established threshold weight;

marking only matched patterns with a weight above the pre-established threshold weight as true matches, which may be relevant for further analysis; and

when an output/alert feature is provided within the graph pattern matching, generating an output/alert which identifies the matched patterns that are true matches.

17. The computer program product of claim 15, further comprising program instructions for:

calculating a score for each matched graph identified;

ranking the score of each matched graph against a pre-established scale for ranking matched graphs; and

outputting a set of resulting matched graphs in order of said ranking using one of a first output scheme, a second output scheme, and a third output scheme, wherein the first output schemes places a higher ranked match graph ahead of a lower ranked matched graph, the second output scheme outputs the matched graphs in reverse order to the first output scheme, and the third output scheme outputs only those matched graphs whose score is above a pre-established minimum score.

18. The computer program product of claim 15, further comprising program instructions for:

identifying a node of interest within the input graph, wherein the node of interest is one of a singular node or a node within a group of interconnected nodes, and wherein said node of interest is inter-connected to other nodes within the social network via one or more interconnection means;

establishing a maximum path length as a first SNA metric that defines the context, wherein said path length represents a number of hops separating the node of interest from a specified node within a matched graph;

determining an actual path length between the node of interest and the specified node within each matched graph identified; and

selecting each matched graph whose path length is not greater than the maximum path length as a true match, wherein matched patterns whose path lengths are greater than the maximum path length are determined to be out-of-context matched graphs that were false positives.

19. The computer program product of claim 18, further comprising program instructions for:

searching only within the maximum path length of the node of interest to find the specified node;

wherein the path length SNA metric is utilized to curtail and filter the matches of the target pattern graph to substantially reduce a number of false positives of matched graphs, which are located outside the path length within the input graph.

20. The computer program product of claim 15, further comprising program instructions for:

identifying an intermediary node that may be neutralized to remove a connection between a first matched pattern and the node of interest, wherein the intermediary node bridges communication between a group represented by the first matched pattern and the node of interest.

21. The computer program product of claim 15, wherein said context comprises one or more SNA metrics including:

SNA metric intervals, which provides at least one of a maximum range and a minimum range from a specified node within which to constrain and focus a search for the matched graphs;

average cycle length;

average path length;

centrality measures;

circumference;

clique measures;

clustering measures;

degree;

density;

diameter;

girth;

number of nodes;

radius; and

radiality.

22. The computer program product of claim 15, further comprising program instructions for:

defining an SNA metric of interest along with a pre-established tracking parameter, such as a threshold;

tracking the SNA metric at each step of completing the graph pattern matching; and

automatically terminating the graph pattern matching when a value of the pre-established tracking parameter exceeds a pre-set threshold for the SNA metric.

23. The computer program product of claim 15, further comprising program instructions for:

providing a range within which a particular SNA metric falls, said range comprising a lower-bound and an upper-bound;

when the range represents an exclusion range, automatically terminating the graph pattern matching when the value for the particular SNA metric falls within the pre-established interval; and

when the range represents an inclusion range, automatically terminating the graph pattern matching when the value for the particular SNA metric falls outside the pre-established interval.

24. The computer program product of claim 15, wherein said program instructions for initiating graph pattern matching further comprises program instructions for:

integrating pre-defined SNA constructs, including groups, into the graph pattern matching, wherein, group membership is accounted for when utilizing SNA metrics to define the match criteria, wherein a match predicate is defined that requires a matched node be a member of a group with certain characteristics;

defining an SNA group that comprises one or more nodes having pre-defined inter-connection characteristics; and

completing the graph pattern matching utilizing the SNA groups as one component of the context.

25. The computer program product of claim 15, further comprising program instructions for one or more of:

defining a particular social role within the social network as a gatekeeper, based on a connection of person, events and activities to a node representing the gatekeeper; and

defining roles for particular nodes within the input graph, including;

a first role, which represents a known entity exhibiting certain known characteristics/tendencies and intentions;

a second role, which represents an entity that has some kind of association with a target node; and

a third role, which represents a next entity that is connected to entities representing both the first role and the second role.

26. The computer program product of claim 25, further comprising program instructions for:

matching nodes against certain SNA roles and positions when completing the graph matching, wherein the nodes include nodes representing entities with high centrality measures, communication gateways, cut-outs, and reach-ability to other particular entities of interest; and

analyzing a node within the input graph against a select node within a target pattern graph using the pre-determined SNA metric to determine if the node in the input graph matches the select node in the target pattern graph.

27. The computer program product of claim 15, further comprising program instructions for:

performing an activity scoring of the matched pattern using SNA metric inputs, wherein said activity scoring increases or decreases an activity score of the matched pattern, said activity score indicating whether a matched pattern is a pattern of interest; and

when the activity is identified within the input graph;

increasing the activity score when the SNA metric is utilized as an additional qualifier for an activity desired to have a higher activity score; and

decreasing the activity score when the SNA metric is utilized as an additional qualifier for an activity desired to have a lower activity score.

28. The computer program product of claim 15, further comprising program instructions for:

determining a degree of centrality of a particular node using a centrality measure;

comparing the degree of centrality against a pre-established threshold value;

tagging the node as a node of interest when the degree of centrality of the particular node is above the pre-established threshold.

29. The computer program product of claim 15, further comprising program instructions for:

generating a viewable interface having therein selectable options, which interface enables setup, interaction and manipulation of the SNA processing with SNA metrics providing the context; and

generating, in user-understandable format, an output of the matched patterns that are true matches according to the provided context.

30. A system comprising:

a processor;

a memory operatively connected to the processor; and

a utility executing on the processor and which provides program means for;

initiating graph pattern matching within an input graph that represents a social network, said graph pattern matching utilizing pre-defined social network analysis (SNA) metrics to provide a context for finding a true match, wherein the graph pattern matching locates one or more matched graphs within the input graph having similar inter-connections among nodes as a target graph pattern; and

analyzing each matched graph using SNA metrics-based context from at least one of local node attributes within the matched graph and non-local node attributes, external to the matched graph, to determine when the matched graph is a true match.

31. The system of claim 30, wherein the program means for analyzing further comprises program means for:

assigning a weight to each matched graph based on a defined context, which defined context takes into consideration an inter-connection of the matched graph to one or more external nodes of interest within the larger input graph, wherein said weight indicates a relative importance of the matched graph within the defined context;

comparing the weight of each matched pattern against a pre-established threshold weight;

marking only matched patterns with a weight above the pre-established threshold weight as true matches, which may be relevant for further analysis; and

when an output/alert feature is provided within the graph pattern matching, generating an output/alert which identifies the matched patterns that are true matches.

32. The system of claim 30, further comprising program means for:

calculating a score for each matched graph identified;

ranking the score of each matched graph against a pre-established scale for ranking matched graphs; and

outputting a set of resulting matched graphs in order of said ranking using one of a first output scheme, a second output scheme, and a third output scheme, wherein the first output schemes places a higher ranked match graph ahead of a lower ranked matched graph, the second output scheme outputs the matched graphs in reverse order to the first output scheme, and the third output scheme outputs only those matched graphs whose score is above a pre-established minimum score.

33. The system of claim 30, further comprising program means for:

identifying a node of interest within the input graph, wherein the node of interest is one of a singular node or a node within a group of interconnected nodes, and wherein said node of interest is inter-connected to other nodes within the social network via one or more interconnection means;

establishing a maximum path length as a first SNA metric that defines the context, wherein said path length represents a number of hops separating the node of interest from a specified node within a matched graph;

determining an actual path length between the node of interest and the specified node within each matched graph identified; and

selecting each matched graph whose path length is not greater than the maximum path length as a true match, wherein matched patterns whose path lengths are greater than the maximum path length are determined to be out-of-context matched graphs that were false positives.

34. The system of claim 33, further comprising program means for:

searching only within the maximum path length of the node of interest to find the specified node;

wherein the path length SNA metric is utilized to curtail and filter the matches of the target pattern graph to substantially reduce a number of false positives of matched graphs, which are located outside the path length within the input graph.

35. The system of claim 30, further comprising program means for:

identifying an intermediary node that may be neutralized to remove a connection between a first matched pattern and the node of interest, wherein the intermediary node bridges communication between a group represented by the first matched pattern and the node of interest.

36. The system of claim 30, wherein said context comprises one or more SNA metrics including:

SNA metric intervals, which provides at least one of a maximum range and a minimum range from a specified node within which to constrain and focus a search for the matched graphs;

average cycle length;

average path length;

centrality measures;

circumference;

clique measures;

clustering measures;

degree;

density;

diameter;

girth;

number of nodes;

radius; and

radiality.

37. The system of claim 30, further comprising program means for:

defining an SNA metric of interest along with a pre-established tracking parameter, such as a threshold;

tracking the SNA metric at each step of completing the graph pattern matching; and

automatically terminating the graph pattern matching when a value of the pre-established tracking parameter exceeds a pre-set threshold for the SNA metric.

38. The system of claim 30, further comprising program means for:

providing a range within which a particular SNA metric falls, said range comprising a lower-bound and an upper-bound;

when the range represents an exclusion range, automatically terminating the graph pattern matching when the value for the particular SNA metric falls within the pre-established interval; and

when the range represents an inclusion range, automatically terminating the graph pattern matching when the value for the particular SNA metric falls outside the pre-established interval.

39. The system of claim 30, wherein said program means for initiating graph pattern matching further comprises program means for:

integrating pre-defined SNA constructs, including groups, into the graph pattern matching, wherein, group membership is accounted for when utilizing SNA metrics to define the match criteria, wherein a match predicate is defined that requires a matched node be a member of a group with certain characteristics;

defining an SNA group that comprises one or more nodes having pre-defined inter-connection characteristics; and

completing the graph pattern matching utilizing the SNA groups as one component of the context.

40. The system of claim 30, further comprising program means for one or more of:

defining a particular social role within the social network as a gatekeeper, based on a connection of person, events and activities to a node representing the gatekeeper; and

defining roles for particular nodes within the input graph, including;

a first role, which represents a known entity exhibiting certain known characteristics/tendencies and intentions;

a second role, which represents an entity that has some kind of association with a target node; and

a third role, which represents a next entity that is connected to entities representing both the first role and the second role.

41. The system of claim 40, further comprising program means for:

matching nodes against certain SNA roles and positions when completing the graph matching, wherein the nodes include nodes representing entities with high centrality measures, communication gateways, cut-outs, and reach-ability to other particular entities of interest; and

analyzing a node within the input graph against a select node within a target pattern graph using the pre-determined SNA metric to determine if the node in the input graph matches the select node in the target pattern graph.

42. The system of claim 30, further comprising program means for:

performing an activity scoring of the matched pattern using SNA metric inputs, wherein said activity scoring increases or decreases an activity score of the matched pattern, said activity score indicating whether a matched pattern is a pattern of interest; and

when the activity is identified within the input graph;

increasing the activity score when the SNA metric is utilized as an additional qualifier for an activity desired to have a higher activity score; and

decreasing the activity score when the SNA metric is utilized as an additional qualifier for an activity desired to have a lower activity score.

43. The system of claim 30, further comprising program means for:

determining a degree of centrality of a particular node using a centrality measure;

comparing the degree of centrality against a pre-established threshold value;

tagging the node as a node of interest when the degree of centrality of the particular node is above the pre-established threshold.

44. The system of claim 30, further comprising program means for:

generating a viewable interface having therein selectable options, which interface enables setup, interaction and manipulation of the SNA processing with SNA metrics providing the context; and

generating, in user-understandable format, an output of the matched patterns that are true matches according to the provided context.