1998 AAAI Fall Symposium on Artificial Intelligence and Link Analysis
Link Analysis
Home
Description
Organizing Committee
Symposium
Dates, times, and places
Why a symposium now?
Who should attend?
Press policy
About AAAI
Orlando Information
Schedule
General format
Specific events
Registration
Instructions
Cost
Form
Link Analysis
Artificial Intelligence
Relevant techniques
Software and Data
Existing software
Useful datasets
References
FAQ
Web sites
Bibliography
Contact
Comments
Subscriptions
Background
Link analysis (Sparrow 1991a, 1991b) is performed by investigators in many areas, from epidemiology to fraud detection, from criminal investigations to the study of social networks. Linkage data is typically modeled as a graph, with nodes representing entities of interest to the domain, and links representing relationships or transactions. Examples might be a collection of telephone toll data (e.g., numbers, times, and duration) subpoenaed for a criminal investigation, a collection of cash transactions to and from bank accounts, a collection of sightings of individuals' meetings, their addresses, and other related commercial or social interactions.
Links as well as nodes may have attributes specific to the domain or relevant to the method of collection. For example, link attributes might indicate the certainty or strength of a relationship, the dollar value of a transaction, or probability of an infection.
Some linkage data may be simple but voluminous (e.g., telephone calls), with a uniformity of node and link types, and a great deal of regularity. Other data may be extremely rich and varied, though sparse (e.g., law enforcement data), with elements possessing many domain-specific attributes as well as confidence and value which may change over time.
Link analysis is distinct from techniques that construct connectionist networks, bayesian belief networks, and association rules. These techniques discover and represent associations based on the aggregate statistical characteristics of a sample of instances drawn from some population. In contrast, link analysis begins with data that can be represented as a network and attempts to infer useful knowledge from the nodes and links of that network.
Link analysis ask questions such as:
- Which nodes are "key" or central to the network?
- Which links can be severed (strengthened) to most effectively impede (enhance) the operation of the network?
- Can the existence of undetected links or nodes be inferred from the known data?
- Are there similarities in the structure of sub-parts of the network which may indicate an underlying relationship (e.g., modus operandi)?
- What are the relevant sub-networks within a much larger network?
- What data model and level of aggregation best reveal certain types of links and subnetworks?
We want to explore the space of AI techniques relevant to the wide variations in the type, quantity, and richness of link analysis data and by the variety of needs of the practitioners of link analysis. For example, heuristic, localized methods might be appropriate for matching known patterns to a network of financial transaction in a criminal investigation. Efficient global search strategies, on the other hand, might be best for finding centrality or severability in a telephone toll network.
In action
Several papers at the Symposium will discuss applications of link analysis, including detecting terrorist threats, classifying Web pages, detecting nuclear proliferation, analyzing transportation routes, detecting money laundering, and finding previously undiscovered medical knowledge.