Systems and methods for large-scale link analysis

Abstract

Systems and methods for accepting relationship indications based on interaction among entities, where each relationship indication specifies that a respective pair of the entities may be related. A single entity record may be constructed that indicates all the linked entities that have been identified as being related to the entity. The entities may include an individual, a set of individuals, a communication terminal, a plurality of communication terminals, an organization, an e-mail address, a Web-site, a bank account and a home address. An analytics operation may performed, such as identifying a shortest sequence of interrelated entities that relate a first entity with a second entity, and acting upon the identified sequence.

What is claimed is: 
     
         1 . A method, comprising:
 accepting a plurality of relationship indications based on interaction among entities, each relationship indication specifying that a respective pair of the entities are related;   using a link processor, identifying for each entity among a group of the entities, based on the relationship indications, one or more linked entities that are related to the entity, and constructing for each entity in the group, a single-entity record that indicates all the linked entities that have been identified as being related to the respective entity;   storing in a memory multiple single-entity records, each single-entity record corresponding respectively to only one of the entities in the group; and   identifying one or more of the entities as targets-of-interest.   
     
     
         2 . The method according to  claim 1 , wherein the interaction comprises communication among the entities over a communication network. 
     
     
         3 . The method according to  claim 1 , wherein the entities comprise at least one entity type selected from a group of types consisting of an individual, a set of individuals, a communication terminal, a plurality of communication terminals, an organization, an e-mail address, a Web-site, a bank account and a home address. 
     
     
         4 . The method according to  claim 1 , wherein constructing the single-entity record comprises storing in the single-entity record respective attributes, which characterize respective relationships between the linked entities and the entity. 
     
     
         5 . The method according to  claim 4 , wherein the attributes indicate respective confidence levels of the relationships. 
     
     
         6 . The method according to  claim 1 , wherein storing the entity records comprises storing at least a portion of the entity records in an in-memory data structure residing in Random Access Memory (RAM), and wherein the method further comprises using the link processor to perform an analytics operation with respect to the entities, wherein the analytics operation comprises querying at least one of the entity records stored in the in-memory data structure. 
     
     
         7 . The method according to  claim 6 , wherein storing the entity records comprises storing another portion of the entity records on a magnetic storage device. 
     
     
         8 . The method according to  claim 7 , wherein performing the analytics operation comprises querying at least a first entity record stored in the in-memory data structure and at least a second entity record stored on the magnetic storage device. 
     
     
         9 . The method according to  claim 1 , wherein the method further comprises using the link processor to perform an analytics operation with respect to the entities, wherein the analytics operation comprises querying at least one of the entity records stored in the memory, identifying a shortest sequence of interrelated entities that relate a first entity with a second entity, and acting upon the identified sequence. 
     
     
         10 . The method according to  claim 1 , wherein the method further comprises using the link processor to perform an analytics operation with respect to the entities, wherein the analytics operation comprises querying the entity records with a query formulated in a graph query language. 
     
     
         11 . The method according to  claim 1 , wherein the method further comprises using the link processor to perform an analytics operation with respect to the targets-of-interest, wherein the analytics operation comprises querying at least one of the entity records stored in the memory. 
     
     
         12 . Apparatus, comprising:
 a memory; and   a link processor, which is configured to accept a plurality of relationship indications based on interaction among entities, each relationship indication specifying that a respective pair of the entities are related, to identify for each entity among a group of the entities, based on the relationship indications, one or more linked entities that are related to the entity, to construct for each entity in the group a single-entity record that indicates all the linked entities that have been identified as being related to the respective entity, to store in the memory multiple single-entity records, each single-entity record corresponding respectively to only one of the entities in the group, and to identify one or more of the entities as targets-of-interest.   
     
     
         13 . The apparatus according to  claim 12 , wherein the interaction comprises communication among the entities over a communication network. 
     
     
         14 . The apparatus according to  claim 12 , wherein the entities comprise at least one entity type selected from a group of types consisting of an individual, a set of individuals, a communication terminal, a plurality of communication terminals, an organization, an e-mail address, a Web-site, a bank account and a home address. 
     
     
         15 . The apparatus according to  claim 12 , wherein the link processor is configured to store in the single-entity record respective attributes, which characterize respective relationships between the linked entities and the entity. 
     
     
         16 . The apparatus according to  claim 15 , wherein the attributes indicate respective confidence levels of the relationships. 
     
     
         17 . The apparatus according to  claim 12 , wherein the memory comprises at least a Random Access Memory (RAM), and wherein the link processor is configured to store at least a portion of the entity records in an in-memory data structure residing in the RAM, and to perform an analytics operation with respect to the entities, wherein the analytics operation comprises querying at least one of the entity records stored in the in-memory data structure. 
     
     
         18 . The apparatus according to  claim 17 , wherein the memory further comprises a magnetic storage device, and wherein the link processor is configured to store another portion of the entity records on the magnetic storage device. 
     
     
         19 . The apparatus according to  claim 18 , wherein the link processor is configured to perform the analytics operation by querying at least a first entity record stored in the in-memory data structure and at least a second entity record stored on the magnetic storage device. 
     
     
         20 . The apparatus according to  claim 12 , wherein the link processor is configured to perform an analytics operation with respect to the entities, wherein the analytics operation comprises querying at least one of the entity records stored in the memory, identifying a shortest sequence of interrelated entities that relate a first entity with a second entity, and acting upon the identified sequence. 
     
     
         21 . The apparatus according to  claim 12 , wherein the link processor is configured to accept a query formulated in a graph query language, and to perform an analytics operation with respect to the entities, wherein the analytics operation comprises querying the entity records with the query. 
     
     
         22 . The apparatus according to  claim 12 , wherein the link processor is configured to perform an analytics operation with respect to the targets-of-interest, wherein the analytics operation comprises querying at least one of the entity records stored in the memory.