Extracting insightful nodes from graphs

• US 9,787,705 B1
• Filed: 08/19/2016
• Issued: 10/10/2017
• Est. Priority Date: 08/19/2016
• Status: Active Grant

• Current Assignee: Quid, Inc. (Netbase Quid)
• Original Assignee: Quid, Inc. (Netbase Quid)
• Inventors: Love, Oriana Jeannette, Tacchi, Ruggero Altair, Chen, Ping
• Primary Examiner(s): Gergiso, Techane
• Application Number:
  US15/241,447
• Time in Patent Office: 417 Days
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

Provided is a process, including: obtaining a clustered graph, wherein each of the nodes has a plurality of respective node attributes other than an identifier of the node; obtaining a designation of a given node attribute from among the plurality of node attributes; identifying a first subset of nodes of the graph as having anomalous values of the given node attribute by comparing values of the given node attribute in the first subset to a distribution of the given node attribute; identifying a second subset of nodes of the graph as having representative values of the given node attribute by comparing values of the given node attribute in the second subset to the distribution of the given node attribute; and sending instructions to a client device to display a representation of the graph.

Claims

1. A method, comprising:

obtaining, with one or more processors, a clustered graph having more than 1,000 nodes and more than 2,000 edges, wherein;

each respective edge connects a respective pair of the nodes, and

each of the nodes has a plurality of respective node attributes other than an identifier of the node;

obtaining, with one or more processors, a designation of a given node attribute from among the plurality of node attributes;

identifying, with one or more processors, a first subset of nodes of the graph as having anomalous values of the given node attribute by comparing values of the given node attribute in the first subset to a distribution of the given node attribute;

identifying, with one or more processors, a second subset of nodes of the graph as having representative values of the given node attribute by comparing values of the given node attribute in the second subset to the distribution of the given node attribute; and

sending, with one or more processors, instructions to a client device to display a representation of the graph, the representation of the graph comprising;

a plurality of clusters of the nodes;

visual identification of at least some nodes of the first subset as being members of the first subset; and

visual identification of at least some nodes of the second subset as being members of the second subset.

2. The method of claim 1, wherein:

the graph comprises more than 5,000 nodes and more than 10 clusters;

the node attributes comprise;

more than 4 non-edge attributes; and

more than 2 edge attributes;

obtaining a designation of a given node attribute from among the plurality of node attributes comprises;

determining mean values of each of the node attributes for each of the clusters;

determining sizes of each of the clusters;

determining distributions of mean values of each of the attributes for random samplings of the size of the clusters from among nodes of the graph, including nodes outside the respective cluster;

based on the distributions, selecting attributes that have mean values that have probabilities in the distributions of less than a threshold amount, wherein different attributes are selected for different clusters;

sending instructions comprises sending instructions to display a force directed layout of clusters of the graph with cluster icons representing the respective clusters and node icons adjacent the cluster icons corresponding to members of the first subset and the second subset;

obtaining a clustered graph comprises obtaining a semantic similarity graph of documents based on semantic similarly of unstructured text in the documents by performing operations comprising;

determining a feature vector for each document, each feature vector having plurality of scores, each score corresponding to a given n-gram and being based on;

an amount of occurrences of the given n-gram in the respective document,

a length of the respective document,

an amount of occurrences of the given n-gram in a plurality of other documents different from the respective document, and

whether the given n-gram is among the set of n-grams pertaining to the selected topic; and

determining an adjacency matrix based on the feature vectors, wherein rows and columns of the adjacency matrix correspond to the documents, values of the feature matrix correspond to a selected-topic-adjusted semantic similarity of documents corresponding to the respective row and column of the values, and values of the feature matrix are based on angles between feature vectors of the documents corresponding to the respective row and column of the values, the operations comprising steps for reducing movement of data across a memory hierarchy.

3. The method of claim 1, wherein at least some of the node attributes are cardinal values indicating a quantity pertaining to an entity represented by the respective node.

4. The method of claim 3, wherein the nodes represent documents and wherein the attributes comprise:

an amount of times the respective document was shared between users.

5. The method of claim 3, wherein the nodes represent businesses and wherein the attributes comprise:

a metric of the respective business'"'"'s performance.

6. The method of claim 1, wherein at least some of the node attributes are values indicating properties of edges connected to the respective node.

7. The method of claim 6, wherein the properties of edges include an amount of edges having greater than a threshold edge weight.

8. The method of claim 6, wherein the properties of edges include an amount of edges extending between clusters of the nodes.

9. The method of claim 1, wherein obtaining a designation of a given node attribute from among the plurality of node attributes comprises:

selecting a cluster from a plurality of clusters of nodes of the graph;

determining measures of central tendency for each of a plurality of attributes of the nodes of the selected cluster;

determining, based at least in part on nodes outside the selected cluster, probabilities of each of the measures of central tendency arising from a sampling of nodes of the graph; and

designating an attribute having a lowest probability among the probabilities as the given node attribute.

10. The method of claim 9, comprising:

determining a number of nodes in the cluster, wherein;

the measure of central tendency is a mean;

sampling comprises forming more than 20 sample groups, each sample group having the number of nodes randomly sampled from the graph;

determining probabilities of each of the measures of central tendency comprises;

determining respective mean values for respective attributes of each of the respective sample groups; and

comparing a mean value of the respective attribute of the cluster to a distribution of means of the respective attribute among the sample groups based on a mean of the mean values of the sample groups and a variance of the mean values of the sample groups.

11. The method of claim 1, wherein obtaining a designation of a given node attribute comprises steps for obtaining a designation of a given node attribute as an insightful node attribute.

12. The method of claim 1, wherein obtaining a designation of a given node attribute comprises steps for obtaining a designation of a given node attribute as an insightful node attribute based on measures of central tendency of node attributes in clusters.

13. The method of claim 1, wherein first subset is a node having a given attribute value closer to a mean value of the given attribute within a given subset of the nodes than a majority of other nodes of the given subset of nodes.

14. The method of claim 13, wherein the given subset corresponds to a cluster of nodes of the graph.

15. The method of claim 1, wherein the second subset of nodes is nodes having outlier values of the given node attribute relative to the respective clusters having nodes in the second subset.

16. The method of claim 1, wherein sending instructions to a client device to display a representation of the graph comprises:

sending instructions to display a force directed layout of the clusters, each cluster being represented by a respective cluster icon;

sending instructions to display a plurality of attribute icons representing the first subset and the second subset adjacent respective cluster icons of clusters including respective members of the first subset.

17. The method of claim 16, wherein:

the cluster icons are connected by lines; and

attribute icons corresponding to edge property attributes are arranged with respect to the lines.

18. The method of claim 16, wherein visual attributes of the attribute icons vary according to:

whether the respective attribute icon represents a representative node for the respective attribute; and

whether the respective attribute icon represents an outlier node for the respective attribute.

19. The method of claim 1, wherein sending instructions to a client device to display a representation of the graph comprises steps for preparing a visual representation of the graph.

20. A system, comprising:

one or more processors; and

memory storing instructions that when executed by at least some of the processors effectuate operations comprising;

obtaining a clustered graph having more than 1,000 nodes and more than 2,000 edges, wherein;

each respective edge connects a respective pair of the nodes, and

each of the nodes has a plurality of respective node attributes other than an identifier of the node;

obtaining a designation of a given node attribute from among the plurality of node attributes;

identifying a first subset of nodes of the graph as having anomalous values of the given node attribute by comparing values of the given node attribute in the first subset to a distribution of the given node attribute;

identifying a second subset of nodes of the graph as having representative values of the given node attribute by comparing values of the given node attribute in the second subset to the distribution of the given node attribute; and

sending instructions to a client device to display a representation of the graph, the representation of the graph comprising;

a plurality of clusters of the nodes;

visual identification of at least some nodes of the first subset as being members of the first subset; and

visual identification of at least some nodes of the second subset as being members of the second subset.