SYSTEMS AND METHODS FOR NETWORK PATTERN MATCHING

• US 20150049634A1
• Filed: 12/31/2012
• Published: 02/19/2015
• Est. Priority Date: 02/20/2012
• Status: Active Grant

• Current Assignee: Aptima Inc.
• Original Assignee: Aptima Inc.
• Inventors: Levchuk, Georgiy, Stacy, E. Webb, Shabarekh, Charlotte
• Granted Patent: US 9,917,739 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods

Abstract

Example embodiments of systems and methods for network pattern matching provide the ability to match hidden networks from noisy data sources using probabilistic multi-attribute graph matching analysis. The algorithms may map roles and patterns to observed entities. The outcome is a set of plausible network models. The pattern-matching methodology of these systems and methods may enable the solution of three challenges associated with social network analysis, namely network size and complexity, uncertain and incomplete data, and dynamic network structure.

Claims

1. A computer implemented method for determining a network pattern match, said method comprising:

representing a plurality of data nodes and a plurality of data links of the data nodes as a data network;

representing a plurality of model nodes and a plurality of model links of the model nodes as at least one model network; and

finding at least one match from the at least one model network to the data network.

2. The computer implemented method of claim 1 wherein:

the data network and the at least one model network are each represented as a multi-attributed graphs; and

finding the at least one match from the at least one model network to the data network comprises utilizing a probabilistic multi-attribute graph matching analysis.

3. The computer implemented method of claim 1 wherein the finding at least one match from the at least one model network to the data network defines at least one attribute for the data node from the at least one model network.

4. The computer implemented method of claim 1 wherein:

the data network and the at least one model network are multi-dimensional matrices;

each data node and each model node is a multi-dimensional vector; and

each data link and each model link is a multi-dimensional vector.

5. The computer implemented method of claim 1 wherein:

the plurality of data nodes and the plurality of model nodes further comprise at least one node attribute;

the plurality of data links and the plurality of model links further comprise at least one link attribute;

the data network and the at least one model network are each represented as a multi-attributed graphs; and

finding the at least one match from the at least one model network to the data network comprises utilizing a probabilistic multi-attribute graph matching analysis.

6. The computer implemented method of claim 5 wherein the finding of at least one match from at least one model network to the data network utilizing a probabilistic multi-attribute graph matching analysis comprises:

defining a network mapping as a binary matrix of a plurality of node mappings between a plurality of model nodes in the model network and a plurality of data nodes in the data network;

defining a network mapping value as a posterior probability of the network mapping;

utilizing a belief propagation algorithm to approximate a distribution of the network mapping values; and

determining the at least one match as the network mapping with the network mapping value which exceeds a network mapping value threshold.

7. The computer implemented method of claim 6 wherein the node mapping is determined by a probability of at least one match between the at least one data node attribute and the at least one model node attribute.

8. The computer implemented method of claim 6 wherein the utilizing a belief propagation algorithm to approximate a distribution of the network mapping values comprises:

determining a marginal posterior probabilities of one of the plurality of node mappings between one of the plurality of model nodes and one of the plurality of data nodes; and

utilizing statistical sampling over the marginal posterior probabilities to determine the network mapping value.

9. The computer implemented method of claim 5 wherein the at least one model link further comprises at least one dependency between one of the plurality of model nodes and another of the plurality of model nodes.

10. The computer implemented method of claim 5 wherein the probabilistic multi-attribute graph matching analysis utilizes a network clustering technique.

11. The computer implemented method of claim 5 wherein:

the data network further comprises at least one data subnetwork; and

finding the at least one match from the at least one model network to the data network utilizing the probabilistic multi-attribute graph analysis comprises;

finding the at least one match from the at least one model network to the data subnetwork utilizing the probabilistic multi-attribute graph analysis.

12. The computer implemented method of claim 5 wherein:

the data network further comprises at least one data subnetwork having at least one data subnetwork node; and

utilizing a belief propagation algorithm to approximate a distribution of the network mapping values comprises;

classifying each data subnetwork node as one of a corresponding node or an irrelevant node;

the corresponding node having a node mapping to a model node of the at least one model network;

the irrelevant node not having a node mapping to a model node of the at least one model network;

determining a correspondence value for each data subnetwork representing a value of the node mapping for the corresponding nodes;

determining a marginal posterior probabilities of one of the plurality of node mappings between one of the plurality of model nodes and each of the corresponding nodes for each data subnetwork exceeding a correspondence value; and

utilizing statistical sampling over the marginal posterior probabilities to approximate a distribution of the network mapping values.

13. The computer implemented method of claim 5 wherein:

the data network further comprises at least one data subnetwork having at least one data subnetwork node;

each data subnetwork node comprising data node attributes;

each model node comprising model node attributes;

the finding the at least one match from the at least one model network to the data network utilizing a probabilistic multi-attribute graph matching analysis comprises;

the plurality of data nodes and the plurality of model nodes further comprise at least one node attribute;

the plurality of data links and the plurality of model links further comprise at least one link attribute;

classifying each data subnetwork node as one of a corresponding node or an irrelevant node;

the corresponding node have a node mapping to a model node of the at least one model network;

the irrelevant node not having a node mapping to a model node of the at least one model network;

determining a correspondence measure for each data subnetwork representing a number of corresponding nodes;

computing a marginal posterior probability estimate on each data subnetwork exceeding a correspondence measure threshold;

utilizing a probabilistic multi-attribute graph matching analysis;

classifying the data subnetwork node by the at least one node attribute of the corresponding node;

determining the at least one node attribute of the corresponding node as a weighted sum of the at least one node attribute of the mapped model node of the at least one model network; and

determining a weighted sum over the attributes of mapped model nodes where the weights are computed based on marginal posterior probability estimates computed utilizing a probabilistic multi-attribute graph matching.

14. The computer implemented method of claim 5 wherein:

the node represents an entity;

the at least one node attribute comprises at least one choice attribute representing a preference for action of the entity;

and the at least one link attribute comprises at least one signal attribute representing a probable observed signal by a sensor of the choice attribute.

15. The computer implemented method of claim 5 wherein the at least one node attribute and the at least one link attribute each further comprise a statistical distribution value.

16. The computer implemented method of claim 5 wherein:

the data node represents a person;

the at least one node attribute represents a preference for action of the person;

the data link represents an observed signal of the person; and

finding at least one match from the at least one model network to the data network infers at least one attribute for the data node from the at least one model network.

17. The computer implemented method of claim 16 wherein:

the preference for action of the person is a profile attribute of the person from a social networking website; and

the observed signal of the person is a communication with another person.

18. A network pattern matching system for determining a network pattern match, the network pattern matching system comprising:

a processor; and

a non-transitory computer readable medium having a computer readable program code embodied therein, said computer readable program code configured to be executed to implement a method comprising;

representing a plurality of data nodes and a plurality of data links of the data nodes as a data network;

representing a plurality of model nodes and a plurality of model links of the model nodes as at least one model network; and

finding at least one match from the at least one model network to the data network.

19. A computer program product for determining a network pattern match comprising a non-transitory computer readable medium having a computer readable program code embodied therein, said computer readable program code configured to be executed to implement a method for determining a network pattern match comprising:

representing a plurality of data nodes and a plurality of data links of the data nodes as a data network;

representing a plurality of model nodes and a plurality of model links of the model nodes as at least one model network; and

finding at least one match from the at least one model network to the data network.