or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
K-core Decomposition and Finding the Maximum Clique in Massive Graphs(Graph theory)
簡介
社交網絡分析的主要關注點之一是識別網絡中具有凝聚力的子群。有凝聚力的子群體是網路的子集,他們之間存在相對強大、直接、強烈、頻繁或積極的聯繫。
k-Core演算法通常用來對一個圖進行子圖劃分,通過去除不重要的節點,將符合逾期的子圖暴露出來進行進一步分析。
Maximum Clique 演算法可以找出最大完全子圖,找出最大完全子圖在計算上是困難的,這是一個np-complete問題。
本次作業要在限定時間內完成在82168個節點的網路中找出節點的coreness與Maximum Clique。
定義k-core子圖
k-core子圖即要求每個節點至少與該子圖中的其他k個節點相關聯。
定義節點的degree
節點的degree即一個節點在網路中和它相關聯的節點的數目。
定義節點的coreness
節點的coreness為k即代表包含這個節點最大的core子圖為k-core子圖。

圖1,圖中藍色的節點的coreness為3、綠色的節點的coreness為2、黃色的節點的coreness為1。
k-core子圖可以由以下psuedo-code得到,
圖2,求解3-core的過程。
根據An O(m) Algorithm for Cores Decomposition of Networks這篇論文

k-core算法可以表示成以下pseudo-code
圖3,k-core算法pseudo-code。
演算法中有兩個地方要做排序,分別是第一種:一開始(1.2),第二種:挑選完節點u之後(2.2.1.2),

尤其是第二種情況可能要執行非常多次(至少在兩個for迴圈內),An O(m) Algorithm for Cores Decomposition of Networks給出一種有效率的方法來減少(1.2)與(2.2.1.2)的時間複雜度,完成k-core演算法。
圖4.高效率k-core演算法。
8~12行 計算出所有節點的max degree為多少,
13~27行 有了max degree後就可以用counting sort完成一開始(1.2)的排序,時間複雜度為O(n)。
圖5.各種陣列的關係
28~41行 原本圖3中挑完節點u之後Vert要重新依照degree做排序,實際上只要做一次交換就可以完成排序。
圖6.
假設原本u的節點為Degree 3,Degree-1為2,把u放在Degree 3的節點的開頭位置(w位置),u就會在Degree 2的節點的最後面,就能以時間複雜度O(1)完成排序。(之後記得更新bin[ ])
圖7.
最後就能以時間複雜度O(n)完成所有節點coreness的計算。
Finding the Maximum Clique
定義Maximum Clique
Maximum Clique subgraph即子圖中的所有節點都與其他節點相關聯。

圖8.Maximum Clique示意圖,節點ABCDE為Maximum Clique。
在維基百科中Bron–Kerbosch algorithm
此演算法採用窮舉所有可能的子圖(當然可以找到解)。時間複雜度 O(n⋅3ⁿᐟ³)。
此算法枚舉了大量不是Maximum Clique的集合,浪費許多時間。
我觀察演算法,發現到一開始就挑到對的節點,後面不是答案的窮舉就可以用Branch and bound省略。
那要怎麼樣找到對的節點呢?
於是我就想到了可以用coreness先將節點做排序,節點coreness為k代表至少該節點有一個subgraph內所有節點都至少是k degree。一個Maximum Clique內若有n個節點,則所有節點的coreness至少都為n,(相反不一定成立,n core subgraph不一定是clique),所以優先挑選coreness最大的節點,會最有可能找到Maximum Clique。
後來順利在時間內完成。
論文參考
寫這篇文章的當下發現說使用coreness與Bron–Kerbosch algorithm中的提到
With vertex ordering是一樣的方法,
degeneracy的定義:
與coreness定義不同但結果相同。
Bron–Kerbosch with degeneracy演算法時間負責度為O(dn^(3d/3)),d為coreness(degeneracy)。
我的演算法結合了Branch and bound與Bron–Kerbosch with degeneracy,與論文Fast Maximum Clique Algorithms for Large Graphs有相似的psuedo-code


該論文表示在真實世界的網路中執行時間在log scale下有接近線性時間。
完整的code:
還可以改善的地方
在
get_max_clique
中的count_max_coreness
時間複雜度為O(n),因為在集合R中的節點已經按照coreness作排列,故要取得max_coreness只要檢查集合R中的最後一個節點即可,可以降低時間複雜度至O(1)。再增加Backtracking演算法,若Q集合的數目加上R集合的數目<已知Maximum Clique的數目,可以直接return。
程式碼100~110行計算節點的Degree時可以直接使用STL vector.size()降低時間複雜度。