--- # System prepended metadata title: Eigenvector-centrality tags: [CHEN Lab] --- --- 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(鄰邊矩陣) > ![](https://i.imgur.com/1ZGyUal.png) > 這個矩陣告訴了我們所有node之間的關係（是否有edge）， 再來我要先算出『Degree Centrality』，也就是如下圖的結果。![](https://i.imgur.com/Ckyyugq.png) > 由於Degree Centrality只能告訴我們每個node上面的edge數量有多少，無法告訴我們我們周圍的node是否有多大的影響力，間接影響我們的數值，因此我必須把==Degree Centrality vector持續的乘adjacency matrix!!!== (如下圖) > ![](https://i.imgur.com/HeOudyk.png) > 那麼為何要這樣做呢？那是因為adjacency matrix擁有著非常好的性質那就是，==他會把有關連的node的數值加成起來==，如果你周圍的node的數值很高，那麼你這個node的數值也會被加成更多！這樣就能顯現出你這個node到底多麽有價值，而非只看你擁有多少edge而已！ > 那麼，為了看看每個node的真實價值到底有多少，我們就持續讓每個算完的vector持續的乘adjacency matrix，把每個node的價值完全榨出來！(下圖) > > ![](https://i.imgur.com/oWsI4kB.png) > 而這個過程就猶如Markov chain一樣，最終會找到一個steady-state，而此時對應到的vector就是我們要求的eigenvector centrality! > > ![](https://i.imgur.com/37PR721.png) > [Centrality] ## Why it is called eigenvector? :::danger :pencil: 根據上面的解釋，完全沒有出現eigenvalue problem呀！怎麼會有eigenvector這個說法呢? ::: > 恩...這是個非常tricky的部分，這需要有一定程度的linear algebra才會比較理解這個原因～ > Actually, 上面我們一直乘adjacency matrix然後找到一個steady-state 這件事情等價於找到一組vector讓下圖的關係式達到最大值![](https://i.imgur.com/jSlOM9P.png) > 註：上圖的C就是adjacency matrix～ > 為何這兩個是等價的呢？那是因為我們一直乘adjacency matrix然後找到穩定態，其實就是找到maximum的Cv值！（上面方法的vector會越乘越大） > 而上面的方法只是限定了我們從(1,1,1,1,1...)這組vector開始找（會這樣做因為我們有算Degree Centrality vector的經驗），來慢慢尋找Cv的最大值；而我們在這裡則是對於一個general的情況下來尋找maximum。 > 好！如果上面可以接受的話，我們就只差最後一步了，也就是解出v。 > 解這個問題很簡單，如下圖～ ![](https://i.imgur.com/kUkV0Xv.png) > 從上圖可以發現，我們其實就是在解一個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)