Link Analysis

Who is friends with whom on instagram or facebook? Which doctors prescribe which drugs to which patients? Which pairs of cities (e.g. London - Paris) generate the most passenger-miles? Which web pages have links that bridge language communities?

These relationships are all visible in data, and they all contain a wealth of information that most data mining techniques are not able to take direct advantage of. In the connected world (where apparently there are no more than six degrees of separation between any two people in the world), understanding relationships and connections is very important! Link analysis is the data mining technique that addresses this need.

Link Analysis and Page rank (Stanford)

Link analysis is based on a branch of mathematics called graph theory, which represents relationships between different objects as edges in a graph. Link analysis is not a specific modeling technique, so it can be used for both directed and undirected data mining. It is often used for creating new derived variables for use by other modeling techniques. It can also be used for undirected data mining, by exploring the properties of the graphs themselves.

Definition: A simple explanation of link analysis, graph networks and databases. In a nutshell, link analysis is a technique used to assess and evaluate connections between data. This is much easier and faster when the data is shown in a graph network, so sometimes link analysis is called network visualization.

Alternative definition

Link analysis is a form of association analysis, in which two or more entities (persons or activities, or things) are associated graphically with the presence of one or more “links” between two entities, and the strength of that link is depicted as lines of different thickness connecting the entities arranges along the circumference of a circle. 

Applications - Example

Link analysis is the most common unsupervised method of fraud detection. The process of performing link analysis is known as link discovery (LD). This discipline has its origin in discreet mathematics, graph theory, social science, and pattern analysis. The object of LD is to find hidden links among patterns that appear to be unrelated.

Link analysis tools - 3 generations

Klerks categorized link analysis tools into 3 generations:

(scroll down to the section on "HISTORY" https://en.wikipedia.org/wiki/Link_analysis)