# Link Analysis

## Link Analysis

* Human knowledge is real, convincing and trustable information
* Hyperlinks contain information about the human judgment
* Social sciences
  * Nodes (persons, organizations)
  * Edges (social interaction)
* e.g. Impact factor in scientific literature

### Early Approach

* Basic Assumptions
  * Hyperlinks contain information about the human judgment of a site
  * The **more incoming** links to a site, the more it is **important**
* **Bray (1996)**
  * **visibility** : number of other sites pointing to it (in-degree)
  * **luminosity** : number of other sites to which it points (out-degree)&#x20;
  * Limitation
    * failure to capture the relative importance of different parents (children) sites
* **Mark**
  * To calculate the score S of a document at vertex v
  * Limitation
    * require DAG, Unreasonable
* **Marchiori**
  * **Hyper information** should complement textual information to obtain the overall information&#x20;
  * Limitation
    * Can’t handle real world cases

## HITS

* Hypertext Induced Topic Selection
* For each vertex v in a subgraph of interest

  $$
  \begin{aligned}
  a(v) &= \text{the authority of } v \\
  h(v) &= \text{the hubness of } v
  \end{aligned}
  $$

  * A site is very **authoritative** if it **receives** many citations
    * citation from important sites weight more.
  * **Hubness** shows the importance of a site
    * good hub **links** to many authoritative sites.

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcXv8ydPvkxJudb3%2FHITS_hub_auth.png?generation=1575975821866615\&alt=media)

### Approach

```
1. rank pages authority according to their in-degree
2. extend the root set to base set
```

* Authority and Hubness will converge
  * mutually reinforcing relationship

    $$
    a(v) := \sum\_{w \in pa\[v]} h(w) \\
    h(v) := \sum\_{w \in ch\[v]} a(w)
    $$
* Let A denote the adjacency matrix of graph

  $$
  \begin{aligned}
  a\_t &:= A^t h\_{t-1} \\
  h\_t &:= A a\_{t-1}
  \end{aligned}
  $$

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcXy_SZVQlxZsiau%2FHITS_adjacency_matrix.png?generation=1575975820328413\&alt=media)

### Examples

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcY-Lap-ZPFJHuBp%2FHITS_example.png?generation=1575975821058306\&alt=media)

```
initial all hubness and authority (h, a) to (1, 1)
loop:
    calculate hubness by children counts
    calculate authority by parent counts
    normalization:
        new h = node's hub / all hub
        new a = node's authority / all authorities
```

* The sites come from high hubness sites will have high authority
* The sites have high hubness will point to many high authority sites

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcY1WeYKjNowtzHU%2FHITS_hub_auth_relation.png?generation=1575975831058651\&alt=media)

### Issues

* Mutually reinforcing relationships between hosts
  * Nepotistic links : 互相幫忙 cite
  * Link normalization
* Will be **solved** by improvements
  * The document can contain many identical links to the same document in another host
  * Links are generated automatically
  * Non-relevant Nodes

### Observation

* The process of link analysis
  * Convergence of values of hubs and authorities&#x20;
  * Two (hub, authority) pairs

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcY3yupUCZJnw212%2FHITS_observation.png?generation=1575975819622573\&alt=media)

### Improvements

* Bharat and Henzinger : Combining Connectivity and Content Analysis
  * Assign weight to identical multiple edges
    * which are inversely proportional to their multiplicity
  * Prune irrelevant nodes or regulating the influence of a node with a relevance weight

## PageRank

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcY5EfuH7mixCHS0%2Fpagerank_intuition.png?generation=1575975824287020\&alt=media)

* The weight is assigned by the rank of **parents**
  * like pipe

    $$
    r(v) = \alpha \sum\_{w \in pa\[v]} \frac{r(w)}{\lvert ch\[w]\rvert}
    $$
* No more hubness & authority weights, only parent rank
* Page rank is propotional to its parent's rank
  * Inversely propotional to its parent's out-degree
* Query Independent

### Examples

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcY75sV7ZfPOCvkz%2Fpagerank_example.png?generation=1575975822699289\&alt=media)

| PR    | ID | OutLink   | InLink  |
| ----- | -- | --------- | ------- |
| 0.304 | 1  | 2,3,4,5,7 | 2,3,5,6 |
| 0.179 | 5  | 1,3,4,6   | 1,4,6,7 |
| 0.166 | 2  | 1         | 1,3,4   |
| 0.141 | 3  | 1,2       | 1,4,5   |
| 0.105 | 4  | 2,3,5     | 1,5     |
| 0.061 | 7  | 5         | 1       |
| 0.045 | 6  | 1,5       | 5       |

* PR value may proportional to in-degrees
* High PR value from high parent's PR value (2, 3, 4, 5, 7 from 1)
* Quick reference

  $$
  \begin{aligned}
  PR(P\_i) &= \frac{d}{n} + (1-d) \times \sum\_{l\_{j,i}\in E} PR(P\_j) / \text{Outdegree}(P\_j) \\
  \text{D(damping factor)} &= 0.1 - 0.15 \\
  n &= \lvert \text{page set}\rvert
  \end{aligned}
  $$

### Stability

* Whether the link analysis algorithms based on eigenvectors are stable in the sense that results don’t change significantly?
  * The **connectivity** of a portion of the graph is **changed** arbitrary
  * How will it affect the results of algorithms?

## SALSA

* Probabilistic extension of the HITS algorithm
  * You can view it as **HITS with normalization**
* Random walk both in the forward and backward direction
* Two separate random walks
  * **Hub** walk
    * a forward link from $$u\_h$$ to $$w\_a$$
    * immediately a backward link from $$w\_a$$ to $$v\_h$$

      $$
      (u, w) \text{ and } (v, w) \in E
      $$
  * **Authority** walk
    * a backward link from $$w\_a$$ to $$u\_h$$
    * immediately a forward link from $$u\_h$$ to $$x\_a$$

      $$
      (u, w) \text{ and } (u, x) \in E
      $$

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcY9tSDkuuhow7Jr%2FSALSA_intuition.png?generation=1575975823549769\&alt=media)

## Limit of Link Analysis

* META tags/ invisible text
  * Search engines relying on meta tags
  * often misled (intentionally) by web developers
* Pay-for-place
  * organizations pay search engines and page rank
  * organizations pay high ranking pages for advertising space&#x20;
* **Stability**
  * **Adding even a small number of nodes/edges to the graph has a significant impact**
* Topic drift
  * A top authority may be a hub of pages on a different topic
  * resulting in increased rank of the authority page
* Content evolution
  * Adding/removing links/content&#x20;
  * affect the intuitive authority rank of a page requiring recalculation of page ranks
  * Incremental link analysis

## Similarity measurement by links

* How similar two objects are within a network
  * How to measure the similarity between two objects based on links relationship
* Based on **linked-structure**
  * object-to-object relations&#x20;
* Based on **textual content**
  * keywords co-currency&#x20;
* **Linked-based** produce systematically better correlation with human judgements compared to the text-based one

## SimRank

* Idea : **Random Surfer model**
* Two objects are similar
  * If they are linked with the same or similar objects
  * Consider : Inlink relationship
* Defined by **recursively** and computed by **iteratively**

$$
S(a,b) = \frac{C}{\lvert I(a) \rvert \lvert I(b)\rvert}
\sum\_{i=1}^{\lvert I(a)\rvert}\sum\_{j=1}^{\lvert I(b)\rvert}
S(I\_i(a), I\_j(b))
$$

* I(a), I(b) : all in-neighbors
* C : decay factor, between 0, 1
* S(a, b) between 0, 1
* S(a, a) = 1

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcYB2_qLNW5IwXws%2Fsimrank_intuition.png?generation=1575975831035457\&alt=media)

## Link analysis in a social network

* Node : entity&#x20;
* Edge : relationship
* We want to know in this social network
  * which nodes/edges are influential/important
  * which node is an outlier

### Centrality

* Degree centrality
  * In-degree, out-degree
* Closeness centrality
  * Geodesic distance between the entity and all other entities
* Betweeness centrality
  * Geodesic path
* Eigenvector centrality
  * Central entity receiving many communications from other wellconnected entities
* Power centrality

$$
NET\_\text{degree} =
\frac{\sum\_{v\in V}\text{Max}\_{v\in V}\text{Degree}(v) - \text{Degree}(v)}{(n-1)\times (n-2)}
$$

### Conductance and NCPP

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcYDgKkIuUPMNeWe%2Fconductance.png?generation=1575975825332481\&alt=media)

* Look at best community (2/8)
* Numerator means the community has 2 out-degree
* Denominator means the community's inner degree is 8

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LvjTawGm06SAlw9IdD3%2F-LvjTcYFmrmacTIEYoLp%2FNCPP.png?generation=1575975826287284\&alt=media)

* NCPP uses conductance to find the best divide of communities
