Patent Publication Number: US-7593909-B2

Title: Knowledge representation using reflective links for link analysis applications

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation in part of and claims the benefit of priority from U.S. application Ser. No. 10/401,104, titled “Data Representation for Improved Link Analysis” and filed Mar. 27, 2003, which is incorporated by reference. 
    
    
     TECHNICAL FIELD 
     This description relates to link analysis, and more particularly to using reflective links for improved link analysis. 
     BACKGROUND 
     In link analysis, data sets may be represented as collections of linked entities, and the topology and connections among the various entities can be analyzed to uncover valuable information. Each entity may symbolize a real world object, such as a person, place, physical object, business unit, phone number, and the like, and each connection between entities may represent an association or relationship between the entities. In general, entities may be represented as nodes and connections as links. Using this type of data representation, a document collection may be represented as documents connected by citations and hypertext links. As another example, an organization may be represented as individuals that are associated according to reporting assignments, social relationships, and communication patterns. 
     Link analysis may be “visual” or “algorithmic.” Visual link analysis presents to an analyst an image of the entities and their connections. The analyst may use the image to discover relationships or otherwise infer new knowledge. Algorithmic link analysis involves a more sophisticated and deeper analysis of the linked entities, such as the distance between two nodes and/or whether two nodes are related through a specific third node. By at least partially automating the process, algorithmic link analysis may facilitate a more efficient evaluation of connections and relationships among entities. 
     Applications of link analysis are typically investigative in nature. For example, terrorist investigations have increasingly involved a study of the relationships among people, common residences, banks, fund transfers, and known terrorist organizations. Link analysis may also be used in other law enforcement or fraud detection efforts to identify associations among individuals and organizations; in epidemiology to discover connections between people, animals, homes, and workplaces; in evaluating complex computer systems; and in information retrieval to analyze relationships among web pages, news stories, or other document collections. Accordingly, link analysis is potentially valuable to a wide variety of enterprises, including, for example, organizations involved with business intelligence and knowledge management. 
     In performing link analysis, one must first develop a topology (e.g., known links between people, things, and events). The topology may be constructed using multiple, heterogeneous data sources. The value of link analysis is in using the topology to predict and infer previously unknown relationships among entities. Such predictions and inferences may be made, for example, by looking at the distance (e.g., the number of links) between entities, a connection between two entities through a specific third entity, or a pattern of events. For example, by examining a set of activities, it may be possible to discover a relationship between entities or to predict an upcoming event. 
     SUMMARY 
     Techniques for representing data for use in link analysis applications may be implemented to provide improved insights about the relationships among entities. Conventional techniques for representing data may be inadequate for effectively representing the characteristics of links that represent relationships between entities or nodes. For example, traditional link analysis models generally use links that merely show a connection between two nodes but that do not contain information about the characteristics of the link. Techniques are provided for using reflective links that provide different characteristics for the links depending on the direction of the link and that provide properties and functions that are associated with the links. 
     In one general aspect, data regarding a knowledge domain may include information about nodes and reflective links. Each node may represent an entity in the knowledge domain. Each reflective link may represent a relationship between a respective specified pair of nodes. The specified pair of nodes may include a first node and a second node. Each reflective link may also include a first set of characteristics for the relationship of the first node to the second node and a second set of characteristics for the relationship of the second node to the first node. The first set of characteristics may be different from the second set of characteristics and may include reflective characteristics of the second set of characteristics. Link analysis may be performed on the nodes and the reflective links to infer new knowledge about the knowledge domain. 
     Implementations may represent one or more of the following features. For example, each reflective link may include a first link from the first node to the second node and a second link from the second node to the first node. The first link may be associated with the first set of characteristics and the second link may be associated with the second set of characteristics. The first set of characteristics may include properties and/or functions associated with the relationship of the first node to the second node and the second set of characteristics may include properties and/or functions associated with the relationship of the second node to the first node. 
     A link analysis module may be operable to perform a search of the nodes and the reflective links to identify reflective links that satisfy selected criteria. The search may also be used to identify nodes based at least in part on an association with a reflective link that satisfies the selected criteria. The link analysis module may be operable to perform the search by iteratively identifying nodes that are linked to a selected starting node, either directly or through one or more intermediate nodes, by one or more reflective links that satisfy the selected criteria. A link reflection look-up table may store information about reflective link characteristics, and the link analysis module may be operable to perform the search by using the information from the link reflection look-up table to identify reflective links that satisfy the selected criteria. 
     A management utility may be used for managing the data regarding the nodes and the reflective links. 
     An extraction utility may be used for extracting node and link data from a data source and storing the node and link data. 
     Link analysis may be performed on the data representing nodes and reflective links by identifying a starting node for a link analysis search and iteratively searching for nodes that are linked to the starting node by one or more links that satisfy the selected criteria. The iterative search may include considering the characterisitics of links in both directions. The selected criteria may relate to one or more selected properties and/or functions. The iterative search may involve searching for links that satisfy the selected criteria in a first direction away from the starting node and searching for links that satisfy the selected criteria in the second direction using information about reflective characteristics of the links in the first direction. For each link, the reflective characteristics may represent predefined characteristics known to be associated with the link in the second direction based on the characteristics of the link in the first direction. The iterative search may also involve searching for nodes that are linked to an intermediate node by a link that satisfies the selected criteria. Each intermediate node may represent a node that is linked to the starting node by one or more of a series of links that satisfy the selected criteria. 
     The search for links in the second direction may be performed only with respect to intermediate nodes for which a link in the first direction that satisfies the selected criteria cannot be found. 
     The described techniques may be implemented, for example, in a system for facilitating link analysis, by a machine-readable medium that stores the information about the nodes and the reflective links, or in a method for performing link analysis. 
     The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features, will be apparent from the description and drawings, and from the claims. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is an illustrative example of a reflective link. 
         FIG. 2 . is an illustrative example of a link diagram. 
         FIG. 3  is a block diagram of a link analysis system. 
         FIG. 4  is a flow diagram of a link analysis process that uses reflective links. 
         FIG. 5A  is an illustrative example of an exhaustive link analysis search process. 
         FIG. 5B  is an illustrative example of a link search process. 
         FIG. 5C  is an illustrative example of a reflective link search process. 
     
    
    
     Like reference symbols in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
     Systems and techniques may be provided for capturing detailed knowledge about relationships between entities in a domain. Essentially, the entire domain may be modeled by nodes and links. 
     A node is defined as any entity in the domain (e.g., a person, place, company, or vehicle) and a link is defined as any relationship between the two nodes (e.g., ownership, employee, sibling, and the like). Nodes do not necessarily need to represent actual physical objects. For example, nodes may also represent characteristics or properties (e.g., a name, phone number, account number, or identification number associated with a person or company). In traditional link analysis techniques, each link is a simple connection between two nodes. For example, an employee and an employer may be “linked” to each other. The nature of the link is often transparent or requires additional objects to define the characteristics of the link. In one previously proposed technique, a third node associated with a link was introduced to capture information about the relationships. 
     In accordance with the described systems and techniques, and unlike traditional link analysis models, information about relationships between nodes is stored using reflective links. A reflective link is a connection between two nodes that may embed different properties and functions based on the direction of the link. Reflective links may represent bidirectional links that conceptually are reciprocals of one another. A reflective link may be represented as a single link that has different properties and/or functions based on the direction of the link. A reflective link will generally possess at least some characteristics (i.e., properties and/or functions) in one direction that are known, or subject to some type of constraint, based on the characteristics in the other direction. Such characteristics that are known or constrained in one direction based on characteristics in the other direction may be referred to as “reflective characteristics.” 
       FIG. 1  is an illustrative example of a reflective link  100 . The reflective link represents a marriage relationship between two people named John and Mary. The reflective link  100  does not merely indicate that John and Mary are married, however. Instead, the reflective link  100  indicates that Mary is John&#39;s wife and that John is Mary&#39;s husband. Thus, the reflective link includes two underlying links—one link  105  indicating that Mary is related to John by a “wife” link and a link  10  in the opposite direction indicated that John is related to Mary by a “husband” link. The illustrated example is relatively simplistic, and specific applications may use reflective links that include more extensive properties and functions. 
     The specific properties and functions embedded in reflective links may vary for different applications. In one implementation, the properties may include a name that identifies the link; a type that identifies the type of the link (e.g., husband); temporal information that identifies any date/time attributes of the link, such as start and/or end dates; location-specific information for the link; a strength attribute that identifies the relative strength of the link; priority data that indicates a priority of the link relative to other links; and security data that controls access to the nodes. The functions may include statistical functions that are used to track the link&#39;s usage statistics, such as frequency of use or distances associated with the link; heuristic functions that are used in validating the applicability of the link for a particular link analysis investigation; neighborhood functions that provide information about the nodes within a particular distance from the link (e.g., located within a small number of links); and visualization functions that provide visual images of the information associated with the link and the nodes associated with the link. In specific implementations, fewer or additional properties and functions may be associated with the reflective links depending upon the available data for a particular relationship and the specific application. 
       FIG. 2 . is an illustrative example of a link diagram  200 . The link diagram  200  is representative of the type of information that may be used in performing link analysis. The link diagram  200  includes a number of nodes that are connected by reflective links. The nodes represent entities (including, in some cases, properties or characteristics) and the reflective links represent relationships among the nodes. Each of the reflective links represents links in two directions and indicates the link type and reflection characteristics of the links, although the reflective link might also include other characteristics. 
     In  FIG. 2 , each reflective link is shown as having a particular designated direction. The designated direction represents a first link having one set of characteristics, while a second link in the opposite direction has reflective characteristics of the first link. In other words, the second link has predefined characteristics (indicated by a parenthetical) that are known or expected to be present based on the characteristics of the first link. For instance, if a link in one direction is “wife,” then it is known that the link in the other direction is “husband.” In some cases, the reflective characteristics may be only a subset of the characteristics associated with the second link. Thus, some characteristics of the second link may be independent of the characteristics of the first link and may not be known from those characteristics. 
     In the example of  FIG. 2 , an XYZ Manufacturing node  202  has an associated reflective link  204  that indicates that XYZ Manufacturing produces a widget product (node  206 ) and that the widget product is produced by XYZ Manufacturing. The XYZ Manufacturing node  202  also has an associated reflective link  208  that indicates that XYZ Manufacturing is a supplier to retailer ABC (node  210 ) and that retailer ABC is a customer of XYZ Manufacturing. 
     Retailer ABC sells the widget product (node  206 ) as indicated by a reflective link  212  and also sells a gadget product (node  214 ) as indicated by another reflective link  216 . The reflective characteristics of the reflective links  212  and  216  indicate that the widget product and the gadget product are sold by Retailer ABC. 
     A reflective link  218  indicates that retailer ABC (node  210 ) is a customer of First Bank (node  220 ) and likewise that First Bank is a vendor for retailer ABC. First Bank is associated with a reflective link  222  indicating that it is located at 111 Central Avenue (node  224 ) and that 111 Central Avenue is the location for First Bank. Another reflective link  226  indicates that the phone number for First Bank is “555-0001” (node  228 ) and that the phone number “555-0001” belongs to First Bank. 
     A node  230  represents a person named John Smith, and reflective links  232  and  234  indicate that John Smith is a customer of retailer ABC (node  210 ) and First Bank (node  220 ), respectively, and that retailer ABC and First Bank are vendors for John Smith. A reflective link  236  indicates that John Smith bought a gadget product (node  214 ) and that the gadget product is owned by John Smith. Another reflective link  238  indicates that John Smith has a social security number of “123-45-6789” (node  240 ) and that the social security number identifies John Smith. Yet another reflective link  242  indicates that John Smith is the husband of Mary Smith (node  244 ), and thus has a wife by that name. A reflective link  246  indicates that Mary Smith is employed by First Bank (node  220 ), which is Mary Smith&#39;s employer. Another reflective link  248  indicates that Mary Smith has a social security number of “123-45-6790” (node  250 ) and that the social security number identifies Mary Smith. Both John Smith (node  230 ) and Mary Smith (node  244 ) have a phone number of “555-1234” (node  256 ), as indicated by reflective links  252  and  254 , and reside at 123 Main Street (node  262 ), as indicated by reflective links  258  and  260 . Similarly, the reflective links  252  and  254  indicate that the phone number “555-1234” belongs to John Smith and Mary Smith, and the reflective links  258  and  260  indicate that 123 Main Street is the residence of John Smith and Mary Smith. 
     Although the illustrated link diagram  200  is in the context of a particular type of domain, virtually any type of domain in which relationships exist among items of data can be represented as a link diagram. The links may contain different levels of information than those illustrated. For example, a link may not indicate that the associated information is, e.g., a social security number; instead, the link may merely represent ownership or some one-to-one correspondence between a person and a social security number. 
     The ultimate purpose of the link diagram, or the information represented in the link diagram, may be to perform some type of link analysis. For example, in the illustrated link diagram, a search of the link diagram  200 , or the information represented by the link diagram  200 , may reveal that there is a link between a certain address (e.g., 123 Main Street (node  262 )) and another item in the domain (e.g., a gadget product (node  214 ) purchased from retailer ABC (node  210 )). Such a search may be performed manually using a visual analysis of the link diagram  200  or using some type of automated or algorithmic analysis, which may be performed using a processor programmed with instructions for performing a search of nodes and links stored in a memory. 
     In performing link analysis, reflective links support improved search and knowledge discovery capabilities by better defining the context of the relationships among the nodes. For example, reflective links may be used to support improved route planning, such as by simplifying airline logistics and pricing using links that have associated properties and functions. In particular, a link analysis may be performed using reflective links to identify an optimal route for travel or shipping by airline to provide a balance among time, cost, and efficient use of resources. In addition, the use of reflective links provides better heuristics (by embedding some prior knowledge in the reflective link, for example). As an example, if one link is of type “husband,” the reflection of that link cannot be of type “brother.” Reflective links can also help provide better look-ahead capabilities by serving as predictive tools. For example, if a person with ties to terrorism is about to take a trip, a reflective link might help predict that a location near the person&#39;s destination is potentially going to be a target of a terrorist attack. 
       FIG. 3  is a block diagram of a link analysis system  300 . The link analysis system  300  includes a data source  305 , an entity/link extraction utility  310 , a node/link management utility  315 , a node/link database  320 , and a link analysis module  325 . The data source  305  is the knowledge domain from which the data for performing link analysis, and for generating the node and link structure, is obtained. The data source  305  may include any number of different sources of data. Initially, the data may be partially consolidated, through manual or electronic entry, in transactional databases, data warehouses, and/or other data storage media. 
     The node/link management utility  315  manages the node and link data. To this end, the node/link management utility  315  may provide a set of tools for operating on the node and link data. In addition, the node/link management utility  315  may implement a set of rules that govern the construction of the node/link database  320 . 
     The entity/link extraction utility  310  extracts information from the data source  305  to identify entity pairs that are related to one another through a link, along with the information regarding the link and any reflective characteristics. The entity/link extraction utility  310  may perform a type of extract, transform, and load (ETL) operation for purposes of populating the node/link database  320 . Generally, the entity/link extraction utility  310  may be application-specific, in that the extraction, transformation, and loading functions are specifically tailored to the type of link analysis to be performed. 
     The node/link database  320  stores the information provided by the entity/link extraction utility  310 . 
     The link analysis module  325  analyzes the data in the node/link database  320 . The link analysis module  325  may include predefined queries and other search tools that facilitate rapid searches through the domain knowledge by traversing node-to-node using the links. For example, the link analysis module  325  may support a search for nodes that fit selected criteria and that are located within a certain number of links of one another. The link analysis module  335  may also support a search through certain types of links (e.g., financial transactions) to identify entities that may be related. Accordingly, the link analysis module  325  generates new knowledge inferred from the data in the node/link database  320 . 
     As an example of the process of inferring new knowledge that may be performed by the link analysis module, the node/link database  320  may store node data representing a number of individuals, a number of bank accounts, and a number of residential addresses. The node/link database  320  may also store link data linking the individuals to deposits to and/or withdrawals from certain bank accounts and linking the individuals to certain residential addresses. One of the individuals may be known to have ties to terrorism. The links may indicate that this individual has made deposits to a bank account and that a second individual has made withdrawals from the same bank account. The second individual and a third individual may also be linked to a particular residential address. By traversing the links, it may be determined that the third individual might have ties to terrorism as a result of his shared residence with an individual (i.e., the second individual) who has made withdrawals from a bank account to which deposits were made by an individual with known ties to terrorism (i.e., the first individual). The potential link between the third individual and terrorism activities may represent new knowledge that is inferred from the node/link database  320 . The use of reflective links in such a link analysis process may provide improved results by helping increase the efficiency of the process. 
     The link analysis system  300  and the techniques associated with the reflective links can be used for a variety of applications. For example, the systems and techniques may be used to enhance business intelligence and knowledge management capabilities. In addition, the systems and techniques can be used to develop a wide range of investigative applications, such as anti-terrorism research, fraud detection, law enforcement investigations, employee background checks, chat room monitoring, competitive analysis, profiling of individuals, companies, and organizations, patent analysis, investment analysis, transportation route optimization, manufacturing process planning, defect root-cause analysis, and intellectual capital harvesting. 
     Various implementations of the systems and techniques described here can be realized in digital electronic circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which may be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device. 
     These computer programs (also known as programs, software, software applications or code) may include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the term “machine-readable medium” refers to any computer program product, apparatus and/or device (e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs)) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term “machine-readable signal” refers to any signal used to provide machine instructions and/or data to a programmable processor. 
     For example, the link analysis system  300  may be implemented in a computer system that includes software executable on a programmable processor. The data source  305  may be implemented in one or more data storage mediums. The entity/link extraction utility  310  and the node/link management utility  315  may be implemented as software that may be executed on a computer or other processor. The entity/link extraction and the node/link management software may operate to store the node/link database  320  on a data storage medium or mediums. In addition, the node/link management utility  315  may provide users with the ability to access tools through a user interface to perform management operations on the data in the node/link database  320 . The link analysis module  325  may also be implemented as software that operates on the data stored in the node/link database  320  and that supports a user interface through which users can execute queries or use other search tools. New inferred knowledge may then be generated as output and displayed on a user interface, such as a display screen, or stored in a database. 
       FIG. 4  is a flow diagram of a link analysis process  400  that uses reflective links. A request for a link analysis is received (step  405 ). The request includes an indication of the starting nodes and the link types or other link characteristics for which the link analysis is to be performed. The link analysis process  400  moves to the starting node (step  410 ) from which a link analysis search will begin. Using the link types or other characteristics identified in the request for the link analysis, the link types that are required to satisfy the search parameters are enumerated (step  415 ). A search for valid links associated with the starting node is then conducted (step  420 ). 
     If a valid link is not found (step  425 ), it is not immediately assumed that no valid links are present. Instead, the process  400  determines link reflections, if available, of the links that are attached to the starting node (step  430 ) using a link reflection look-up table  435 . Thus while, the link search is performed initially on characteristics of the links in a direction away from the starting node, link reflections may be used to perform the search on links in a direction toward the starting node. 
     The link reflection look-up table  435  stores information about reflective characteristics of different types of links. For example, for a link of type “husband,” the link reflection look-up table  435  would store information indicating that the reflection is “wife.” Similarly, other properties and functions may have reflective characteristics. For example, a link in one direction may include some type of calculation, while the reflection may include a different type of calculation. By looking up link reflections, the search for valid links can also include searching the characteristics of links in the opposite direction (i.e., in a direction toward the starting node). Searching the links in both directions helps ensure that valid links are not missed. 
     If a valid link is found in either direction (step  440 ), the search moves to the node at the other end of the found link as the new starting node (step  445 ). The process  400  then returns to step  415  to perform another iteration of the search process from the new starting node (step  450 ). Each new starting node after the initial starting node may be referred to as an intermediate node. The process  400  continues in this manner by searching for additional intermediate nodes until no further valid links can be found. The nodes and links that represent valid paths are then recorded (step  455 ). An analysis of the path information may be performed (step  460 ), from which new knowledge may be identified or inferred and reported to a user of the link analysis process (step  465 ). 
       FIGS. 5A-5C  illustrate different types of link search strategies on the same domain. In general, the search strategy relates to a determination of which paths are selected as the search travels from node to node.  FIG. 5A  is an illustrative example of an exhaustive link analysis search process  505 . In an exhaustive search, all links and nodes in the entire domain are searched. As a result, the number of links being searched expands exponentially. The exhaustive search process  505  therefore finds every link and node that may be relevant but is very time consuming, may not be practical from a cost perspective, and may return too many false positives (i.e., the search identifies links that satisfy the search criteria but that are not relevant to the analysis). 
       FIG. 5B  is an illustrative example of a link search process  510  that represents another possible search strategy that is a more traditional approach. In a link search, the search begins from a starting node and locates links that emanate from the starting node. If a valid link is found, then the search continues from the node at the other end of the found link. However, if a valid link is not found, the search ends at that node. The link search process  510  is very quick but can miss valid nodes. 
       FIG. 5C  is an illustrative example of a reflective link search process  515 . The reflective link search is similar to the link search process  510  except that the search does not end if a valid link is not found in a first direction. Instead, the reflective characteristics of the links are also searched to determine whether the reflective links satisfy the search criteria. In this example, relevant nodes  5 ,  8 , and  12  that were missed using the link search process  510  of  FIG. 5B  are found when using the reflective link search process  515 . The reflective link search process  515  is therefore quick and finds only the relevant nodes. 
     A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made. For example, link analysis may be performed using characteristics of both the nodes and the reflective links to identify relevant paths. Accordingly, other implementations are within the scope of the following claims.