在上一篇文章介紹了在 Neo4j 做資料分析前的準備動作，評估記憶體用量和建立子圖，今天我們就來嘗試其中兩個演算法，中心位置演算法的 Page Rank 和群聚分析演算法的 Label Propagation。

操作 GDS 演算法的語法結構如下

CALL gds.<algo-name>.<mode>(
  graphName: String,
  configuration: Map
)

• algo-name
  使用的演算法名稱
• mode 執行演算法的方式
  • stream
    執行演算法並回傳結果
  • stats
    只顯示該次運算的一些統計資料，不會傳回運算結果
  • mutate
    把運算結果寫回記憶體中的子圖形
  • write
    把運算結果寫回原本的圖形資料庫
• graphName
  已經建立的子圖名稱
• configuration
  與該演算法相關的其他設定，根據演算法的不同，而有不同的設定值

Neo4j GDS - PageRank algorithm

Page Rank 是 Google 早期對網頁排名所採用的演算法，其原理是，一個網頁被其他網頁參考並連結的次數愈多，意義上相當於被其他頁面「投票」，那麼該頁面的重要性就會愈高；而來源網頁的重要性愈高，被投票的網頁重要性也會增加。

該演算法當然不是只能用在網頁，他可以衡量特定範圍內每個元素的相關重要性，不過前提是這些元素彼此之間是有許多連結關係的。

找到前十位最重要的人物（節點）

CALL gds.pageRank.stream('got-interactions') YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC LIMIT 10

找到前十位最重要人物，並列出他們的互動關係數量

CALL gds.pageRank.stream('got-interactions') YIELD nodeId, score
WITH gds.util.asNode(nodeId) AS n, score
MATCH (n)-[i:INTERACTS]-()
RETURN n.name AS name, score, count(i) AS interactions
ORDER BY score DESC LIMIT 10

從 PageRank 演算法的執行結果看出，並不是愈多互動關係的人物，其重要性就愈高。

確認過執行結果後，可以將結果永久儲存回原圖形資料庫，請注意這不是存回記憶體內的 got-interactions 子圖：

CALL gds.pageRank.write('got-interactions', {writeProperty: 'pageRank'})

Neo4j GDS - Label Propagation algorithm

Neo4j GDS 在群聚分析的演算中，目前比較成熟的有

• Louvain
• Label Propagation
• Weakly Connected Components
• Triangle Count
• Local Clustering Coefficient

官網的範例中介紹的是 Label Propagation（標籤傳播）。其原理是，一開始每個節點各自屬於某種「社群標籤」，接下來會不斷的迭代，在每次的迭代中會將每個節點的標籤改為，與其相連的所有點中，最多的標籤，在多次迭代後，最後剩下少數幾種標籤，便完成了群聚分析。

建立新的子圖，需要所有人物節點與 INTERACTS 關係及其 weight 屬性。weight 的意義代表著人物之間的互動次數，在 LPA 演算法中，也將影響相鄰的節點最後是否會被歸在同一群。

// GDS ver 1.8
CALL gds.graph.create(
  'got-interactions-weighted',
  'Person',
  {
    INTERACTS: {
      orientation: 'UNDIRECTED',
      properties: 'weight'
    }
  }
)

// GDS ver 2.0+
CALL gds.graph.project(
  'got-interactions-weighted',
  'Person',
  {
    INTERACTS: {
      orientation: 'UNDIRECTED',
      properties: 'weight'
    }
  }
)

以下指定跑 5 次迭代，差不多就可以得到分群結果。至於實際上該迭代幾次，還是得看資料結構和特性，只能自己實驗看看了。官網有一個只迭代 1 次的範例，可以想像其結果是非常粗略的，把所有人物分散到一千多個群。

CALL gds.labelPropagation.stream(
  'got-interactions-weighted',
  {
    relationshipWeightProperty: 'weight',
    maxIterations: 5
  }
) YIELD nodeId, communityId
RETURN communityId, count(nodeId) AS size
ORDER BY size DESC
LIMIT 5

Neo4j GDS - Label Propagation algorithm with Seed

LPA 演算法允許每個節點一開始就有一個社群標籤作為參考，這很適合用在資料量大且變動性很高的資料庫，就像是把數次迭代後的結果，先存回資料庫，待下次運算時再拿回來參考，而不用每次都從頭開始迭代，重新分析。

因此，我們要先把群聚分析的結果寫回原資料庫的屬性 community

CALL gds.labelPropagation.write(
  'got-interactions-weighted',
  {
    relationshipWeightProperty: 'weight',
    maxIterations: 5,
    writeProperty: 'community'
  }
)

接著再建立新的子圖

// GDS ver 1.8
CALL gds.graph.create(
  'got-interactions-seeded',
  {
    Person: {
      properties: 'community'
    }
  },
  {
    INTERACTS: {
      orientation: 'UNDIRECTED',
      properties: 'weight'
    }
  }
)

// GDS ver 2.0+
CALL gds.graph.project(
  'got-interactions-seeded',
  {
    Person: {
      properties: 'community'
    }
  },
  {
    INTERACTS: {
      orientation: 'UNDIRECTED',
      properties: 'weight'
    }
  }
)

根據 Seed 資料再次做群聚分析

CALL gds.labelPropagation.stream(
  'got-interactions-seeded',
  {
    relationshipWeightProperty: 'weight',
    maxIterations: 1,
    seedProperty: 'community'
  }
) YIELD nodeId, communityId
RETURN communityId, count(nodeId) AS size
ORDER BY size DESC
LIMIT 5

以上分享的都是官網 Sandbox 的範例與資料，這邊沒打算把各種演算法都跑一遍
請大家有興趣自行參考官網教學喔，還有其他各種有趣的演算法和範例～

:play https://guides.neo4j.com/sandbox/graph-data-science

參考來源：
https://neo4j.com/graph-data-science-library/
https://neo4j.com/docs/graph-data-science/current/
https://github.com/neo4j/graph-data-science/
https://medium.com/neo4j/hands-on-with-the-neo4j-graph-data-science-sandbox-7b780be5a44f