Systems and methods for network pattern matching

• US 9,917,739 B2
• Filed: 12/31/2012
• Issued: 03/13/2018
• 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
• Primary Examiner(s): BLANTON, JOHN D
• Application Number:
  US14/379,503
• Publication Number:
  US 20150049634A1
• Time in Patent Office: 1,898 Days
• 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;

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

at least one of the plurality of data nodes represent an entity;

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

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

the at least one link attribute comprises at least one signal attribute representing a probable observed signal by a sensor;

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

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

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

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 at least one of the plurality of data nodes from the at least one model network.

4. The computer implemented method of claim 1 wherein:

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 probabilistic multi-attribute graph matching analysis utilizes a network clustering technique.

6. The computer implemented method of claim 1 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.

7. The computer implemented method of claim 1 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;

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 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 at least one of the data subnetwork nodes 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 of weights 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.

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

9. The computer implemented method of claim 1 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 a probable observed signal of the person; and

finding the 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.

10. The computer implemented method of claim 9 wherein:

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

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

11. The computer implemented method of claim 1 wherein:

at least one of the data nodes represents a person; and

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

12. The computer implemented method of claim 1 wherein the data network and the at least one model network each comprise a multi-node network.

13. The computer implemented method of claim 1 further comprising:

determining a prioritized data collection plan for the data network based on the at least one match;

the data collection plan defines a query attribute of at least one of the data nodes of the data network;

communicating the prioritized data collection plan to a remote device;

receiving a value of the query attribute at the remote device;

updating the data network with the value of the query attribute;

wherein the sensor comprises an unmanned vehicle;

wherein the data node represents a person; and

wherein the data link represents an observed signal of the person.

14. The computer implemented method of claim 1 wherein the plurality of data nodes and the plurality of data links of the data nodes represent a plurality of user profile attributes of a user of a social network.

15. 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;

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;

at least one of the plurality of data nodes represent an entity;

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

the at least one link attribute comprises at least one signal attribute representing a probable observed signal by a sensor;

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

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

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 at least one 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.

16. The computer implemented method of claim 15 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.

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

determining a marginal posterior probability 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 probability to determine the network mapping value.

18. The computer implemented method of claim 15 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 the correspondence value; and

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

19. 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;

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

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

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

the at least one link attribute comprises at least one signal attribute representing a probable observed signal by a sensor;

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

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

wherein at least one of the plurality of model links further comprises at least one dependency between one of the plurality of model nodes and another of the plurality of model nodes.

20. 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;

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

at least one of the plurality of data nodes represent an entity;

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

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

the at least one link attribute comprises at least one signal attribute representing a probable observed signal by a sensor;

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

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