In network theory, link analysis is a data-analysis technique used to evaluate
relationships between nodes. Relationships may be identified among
various types of nodes, including organizations, people and transactions.
Link analysis has been used for investigation of criminal activity,
computer security analysis, search engine optimization, market research,
medical research, and art. Knowledge discovery
Knowledge discovery is an iterative and interactive process used to identify,
analyze and visualize patterns in data. Network analysis, link analysis and
social network analysis are all methods of knowledge discovery, each a
corresponding subset of the prior method. Most knowledge discovery methods
follow these steps: Data processing
Transformation Analysis
Visualization Data gathering and processing requires
access to data and has several inherent issues, including information overload
and data errors. Once data is collected, it will need to be transformed into a
format that can be effectively used by both human and computer analyzers.
Manual or computer-generated visualizations tools may be mapped from
the data, including network charts. Several algorithms exist to help with
analysis of data – Dijkstra’s algorithm, breadth-first search, and depth-first
search. Link analysis focuses on analysis of
relationships among nodes through visualization methods. Here is an
example of the relationships that may be mapped for crime investigations:
Link analysis is used for 3 primary purposes:
Find matches in data for known patterns of interest;
Find anomalies where known patterns are violated;
Discover new patterns of interest. History
Klerks categorized link analysis tools into 3 generations. The first generation
was introduced in 1975 as the Anacpapa Chart of Harper and Harris. This method
requires that a domain expert review data files, identify associations by
constructing an association matrix, create a link chart for visualization
and finally analyze the network chart to identify patterns of interest. This
method requires extensive domain knowledge and is extremely
time-consuming when reviewing vast amounts of data.
In addition to the association matrix, the activities matrix can be used to
produce actionable information, which has practical value and use to
law-enforcement. The activities matrix, as the term might imply, centers on the
actions and activities of people with respect to locations. Whereas the
association matrix focuses on the relationships between people,
organizations, and/or properties. The distinction between these two types of
matrices, while minor, is nonetheless significant in terms of the output of
the analysis completed or rendered. Second generation tools consist of
automatic graphics-based analysis tools such as IBM i2 Analyst’s Notebook,
Netmap, SVAT and Watson. These tools offer the ability to automate the
construction and updates of the link chart once an association matrix is
manually created, however, analysis of the resulting charts and graphs still
requires an expert with extensive domain knowledge.
The third generation of link-analysis tools allow the automatic visualization
of linkages between elements in a data set, that can then serve as the canvas
for further exploration or manual updates.
Applications FBI Violent Criminal Apprehension
Program Iowa State Sex Crimes Analysis System
Minnesota State Sex Crimes Analysis System
Washington State Homicide Investigation Tracking System
New York State Homicide Investigation & Lead Tracking
New Jersey Homicide Evaluation & Assessment Tracking
Pennsylvania State ATAC Program. Violent Crime Linkage Analysis System
Issues with link analysis = Information overload =
With the vast amounts of data and information that are stored
electronically, users are confronted with multiple unrelated sources of
information available for analysis. Data analysis techniques are required to make
effective and efficient use of the data. Palshikar classifies data analysis
techniques into two categories – statistical and artificial intelligence
techniques. Bolton & Hand define statistical data
analysis as either supervised or unsupervised methods. Supervised
learning methods require that rules are defined within the system to establish
what is expected or unexpected behavior. Unsupervised learning methods review
data in comparison to the norm and detect statistical outliers. Supervised
learning methods are limited in the scenarios that can be handled as this
method requires that training rules are established based on previous patterns.
Unsupervised learning methods can provide detection of broader issues,
however, may result in a higher false-positive ratio if the behavioral
norm is not well established or understood.
Data itself has inherent issues including integrity and continuous
changes. Data may contain “errors of omission and commission because of
faulty collection or handling, and when entities are actively attempting to
deceive and/or conceal their actions”. Sparrow highlights incompleteness, fuzzy
boundaries and dynamic changes as the three primary problems with data
analysis. Once data is transformed into a usable
format, open texture and cross referencing issues may arise. Open
texture was defined by Waismann as the unavoidable uncertainty in meaning when
empirical terms are used in different contexts. Uncertainty in meaning of
terms presents problems when attempting to search and cross reference data from
multiple sources. The primary method for resolving data
analysis issues is reliance on domain knowledge from an expert. This is a very
time-consuming and costly method of conducting link analysis and has
inherent problems of its own. McGrath et al. conclude that the layout and
presentation of a network diagram have a significant impact on the user’s
“perceptions of the existence of groups in networks”. Even using domain experts
may result in differing conclusions as analysis may be subjective.
= Prosecution vs. crime prevention = Link analysis techniques have primarily
been used for prosecution, as it is far easier to review historical data for
patterns than it is to attempt to predict future actions.
Krebs demonstrated the use of an association matrix and link chart of the
terrorist network associated with the 19 hijackers responsible for the September
11th attacks by mapping publicly available details made available
following the attacks. Even with the advantages of hindsight and publicly
available information on people, places and transactions, it is clear that there
is missing data. Alternatively, Picarelli argued that use
of link analysis techniques could have been used to identify and potentially
prevent illicit activities within the Aum Shinrikyo network. “We must be
careful of ‘guilt by association’. Being linked to a terrorist does not prove
guilt – but it does invite investigation.” Balancing the legal
concepts of probable cause, right to privacy and freedom of association
become challenging when reviewing potentially sensitive data with the
objective to prevent crime or illegal activity that has not yet occurred.
Proposed solutions There are four categories of proposed
link analysis solutions: Heuristic-based
Template-based Similarity-based
Statistical Heuristic-based tools utilize decision
rules that are distilled from expert knowledge using structured data.
Template-based tools employ Natural Language Processing to extract details
from unstructured data that are matched to pre-defined templates.
Similarity-based approaches use weighted scoring to compare attributes and
identify potential links. Statistical approaches identify potential links
based on lexical statistics. = CrimeNet explorer =
J.J. Xu and H. Chen propose a framework for automated network analysis and
visualization called CrimeNet Explorer. This framework includes the following
elements: Network Creation through a concept space
approach that uses “co-occurrence weight to measure the frequency with which two
words or phrases appear in the same document. The more frequently two words
or phrases appear together, the more likely it will be that they are
related”. Network Partition using “hierarchical
clustering to partition a network into subgroups based on relational strength”.
Structural Analysis through “three centrality measures to identify central
members in a given subgroup. CrimeNet Explorer employed Dijkstra’s
shortest-path algorithm to calculate the betweenness and closeness from a single
node to all other nodes in the subgroup. Network Visualization using Torgerson’s
metric multidimensional scaling algorithm.
References External links
Bartolini, I; Ciaccia, P. "Imagination: Accurate Image Annotation Using
Link-Analysis Techniques". CiteSeerX: 10.1.1.63.2453.
Elink Schuurman MW, Srisaenpang S, Pinitsoontorn S, Bijleveld I,
Vaeteewoothacharn K, Methapat C., The rapid village survey in tuberculosis
control, Tuber Lung Dis. 1996 Dec;77(6):549-54.
Gunhee, K., Faloutsos, C, Hebert, M, Unsupervised Modeling of Object
Categories Using Link Analysis Techniques.
McGehee, R., Intelligence Report. Ressler, S., Social Network Analysis as
an Approach to Combat Terrorism: Past, Present and Future Research.
RFFlow, How to Draw a Link Analysis Diagram.
IBM i2 Analyst's Notebook Premium Silberschatz, A. "What Makes Patterns
Interesting in Knowledge Discovery Systems". CiteSeerX: 10.1.1.53.2780.
Terrorist & Rebel Link Analysis Feed Workshop on Link Analysis: Dynamics and
Static of Large Networks August 20, 2006 Van Meter, Karl M.,
Terrorists/Liberators: Researching and dealing with adversary social networks,
Connections 24(3): 66-78.