---
tags: CHEN Lab
---

# Eigenvector-centrality
- [TOC]

## What is eigenvector-centrality?
> 在一個social network中，每個node所代表的==影響力==有多大有許多不同的表示方法，而在此我們用來判斷node影響力的方式是根據此==node的edge數量==加上==周圍node的影響力==所計算出來的，也就是說：**當你周圍的node越大排，你的價值就會越高。**
> 那麼到底該怎麼計算呢？請往下看～

## How to compute?
> 首先，我們要先算出這個social network的adjacency matrix(鄰邊矩陣)
> 

> 這個矩陣告訴了我們所有node之間的關係（是否有edge）， 再來我要先算出『Degree Centrality』，也就是如下圖的結果。

> 由於Degree Centrality只能告訴我們每個node上面的edge數量有多少，無法告訴我們我們周圍的node是否有多大的影響力，間接影響我們的數值，因此我必須把==Degree Centrality vector持續的乘adjacency matrix!!!== (如下圖)

> 
> 那麼為何要這樣做呢？那是因為adjacency matrix擁有著非常好的性質那就是，==他會把有關連的node的數值加成起來==，如果你周圍的node的數值很高，那麼你這個node的數值也會被加成更多！這樣就能顯現出你這個node到底多麽有價值，而非只看你擁有多少edge而已！
> 那麼，為了看看每個node的真實價值到底有多少，我們就持續讓每個算完的vector持續的乘adjacency matrix，把每個node的價值完全榨出來！(下圖)
>
> 
> 而這個過程就猶如Markov chain一樣，最終會找到一個steady-state，而此時對應到的vector就是我們要求的eigenvector centrality!
>
> 
> [Centrality]

## Why it is called eigenvector?
:::danger
:pencil:
根據上面的解釋，完全沒有出現eigenvalue problem呀！怎麼會有eigenvector這個說法呢?
:::
> 恩...這是個非常tricky的部分，這需要有一定程度的linear algebra才會比較理解這個原因～
> Actually, 上面我們一直乘adjacency matrix然後找到一個steady-state 這件事情等價於找到一組vector讓下圖的關係式達到最大值
> 註：上圖的C就是adjacency matrix～

> 為何這兩個是等價的呢？那是因為我們一直乘adjacency matrix然後找到穩定態，其實就是找到maximum的Cv值！（上面方法的vector會越乘越大）
> 而上面的方法只是限定了我們從(1,1,1,1,1...)這組vector開始找（會這樣做因為我們有算Degree Centrality vector的經驗），來慢慢尋找Cv的最大值；而我們在這裡則是對於一個general的情況下來尋找maximum。

> 好！如果上面可以接受的話，我們就只差最後一步了，也就是解出v。
> 解這個問題很簡單，如下圖～

> 從上圖可以發現，我們其實就是在解一個eigenvalue problem，而且我們要找的是**最大的eigenvalue所對應的eigenvector～** [PCA]

## Conclusion
> eigenvector centrality的由來是非常複雜的，他原先的概念非常簡單，就只是表達一個node的重要性不能只看他自己，也要看他周圍的node到底有多重要；但是搭配了線性代數的概念後，一切都變的複雜了許多，但也美了非常多！！！（解eigenvalue problem比起解markov chain的steady-state還要來得簡單）

## Reference
- [Centrality](http://www.jsums.edu/nmeghanathan/files/2015/08/CSC641-Fall2015-Module-2-Centrality-Measures.pdf?x61976)
- [PCA](https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8-%E7%B5%B1%E8%A8%88%E5%AD%B8%E7%BF%92-%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90-principle-component-analysis-pca-58229cd26e71)