System, method and computer program for analysing and visualising data

• US 8,639,695 B1
• Filed: 07/08/2011
• Issued: 01/28/2014
• Est. Priority Date: 07/08/2010
• Status: Active Grant

• Current Assignee: PATENT ANALYTICS HOLDING PTY LTD
• Original Assignee: PATENT ANALYTICS HOLDING PTY LTD
• Inventors: Spielthenner, Doris
• Primary Examiner(s): Beausoliel, Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US13/179,437
• Time in Patent Office: 935 Days
• Field of Search: 707/748
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A method for identifying clusters within a network including a plurality of nodes and links, comprising the steps of:

• • determining a link value for each node in the network;
  • determining a local maxima within the network by locating node values where the sum of link values are higher than the sum of link values for all adjacent nodes;
  • determining a list of the shortest pathways between a local maximum and all other nodes in the network;
  • collapsing the pathways in accordance with a predetermined algorithm; and
  • associating all nodes that remain connected to each local maximum along the pathways.

Claims

1. A method for identifying clusters within a network including a plurality of nodes and links, comprising the steps of:

determining a link value for each node in the network, with each node being characterized such that it does not require the sharing of an attribute value to be clustered;

determining a local maxima within the network by locating node values where the sum of link values are higher than the sum of link values for all adjacent nodes;

determining a list of the shortest pathways between a local maximum and all other nodes in the network, wherein a pathway embodies a rate of change of link values and is able to traverse a plurality of linked nodes;

collapsing the pathways in accordance with a predetermined algorithm; and

associating all nodes that remain connected to each local maximum along the pathways.

2. A method in accordance with claim 1, wherein the link value is derived by determining the number of second degree of separation links between each node and each other node.

3. A method in accordance with claim 1, wherein the predetermined algorithm collapses the pathways where the rate of change of link values is greater than a predetermined value.

4. A method in accordance with claim 1, wherein the predetermined algorithm collapses the pathways where the link value is smaller than a predetermined value.

5. A method for identifying clusters in accordance with claim 1, wherein the relative ranking of the nodes is determined by:

determining the shortest pathway between each of the nodes;

determining the number of times each of the nodes appears in this list of the shortest pathways; and

assigning a ranking to each of the nodes based on the number of times the node appears in the list of shortest pathways.

6. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

an executable portion configured to determine a link value for each node in the network, with each node being characterized such that it does not require the sharing of an attribute value to be clustered;

an executable portion configured to determining a local maxima within the network by locating node values where the sum of link values are higher than the sum of link values for all adjacent nodes;

an executable portion configured to determining a list of the shortest pathways between a local maximum and all other nodes in the network, wherein a pathway embodies a rate of change of link values and is able to traverse a plurality of linked nodes;

an executable portion configured to collapsing the pathways in accordance with a predetermined algorithm; and

an executable portion configured to associating all nodes that remain connected to each local maximum along the pathways.

7. A method for determining the probability of a data record being associated with another data record, comprising the steps of

determining the length of the shortest pathway value and the number of unique pathways of the shortest length between the two data records, wherein a pathway embodies a rate of change of link values and is able to traverse a plurality of linked data records;

dividing the shortest pathway length by the number of unique pathways to determine a pathway value,

wherein the pathway value is an indicator of the similarity between the selected data record and the at least one other data record.

8. A system for identifying clusters within a network including a plurality of nodes and links, comprising:

a processor arranged to determine a link value for each node in the network, with each node being characterized such that it does not require the sharing of an attribute value to be clustered;

determine a local maxima within the network by locating node values where the sum of link values are higher than the sum of link values for all adjacent nodes;

determine a list of the shortest pathways between a local maximum and all other nodes in the network, wherein a pathway embodies a rate of change of link values and is able to traverse a plurality of linked nodes;

collapse the pathways in accordance with a predetermined algorithm; and

associate all nodes that remain connected to each local maximum along the pathways.

9. A system in accordance with claim 8, wherein the link value is derived by determining the number of second degree of separation links between each node and each other node.

10. A system in accordance with claim 8, wherein the predetermined algorithm collapses the pathways where the rate of change of link values is greater than a predetermined value.

11. A system in accordance with claim 8, wherein the predetermined algorithm collapses the pathways where the link value is smaller than a predetermined value.

12. A system for identifying clusters in accordance with claim 8, wherein the relative ranking of the nodes is determined by:

determine the shortest pathway between each of the nodes;

determine the number of times each of the nodes appears in this list of the shortest pathways; and

assign a ranking to each of the nodes based on the number of times the record appears in the list of shortest pathways.

13. A system for determining the probability of a data record being associated with another data record, comprising:

a processor arranged to determine the length of the shortest pathway value and the number of unique pathways of the shortest length between the two data records, wherein a pathway embodies a rate of change of link values and is able to traverse a plurality of linked data records; and

divide the shortest pathway length by the number of unique pathways to determine a pathway value,

wherein the pathway value is an indicator of the similarity between the selected data record and the at least one other data record.