# 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得到，
```
Input：圖G，
for(核心度k=1,2,3,...)
Step 1：將圖G中度數小於k的頂點全部移除，得到子圖G'。
Step 2：將圖G'中度數小於k的頂點全部移除，得到新子圖G''。該子圖G''就是最終k-Core劃分的結果子圖。
```
圖2，求解3-core的過程。
根據[An O(m) Algorithm for Cores Decomposition of Networks](https://arxiv.org/pdf/cs/0310049.pdf?fbclid=IwAR02bLrnHrf4jOZkMef0DB2Q-CjCNMbI2bvoO2I5NghP7K-W8q02b4HsdDU)這篇論文
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](https://arxiv.org/pdf/cs/0310049.pdf?fbclid=IwAR02bLrnHrf4jOZkMef0DB2Q-CjCNMbI2bvoO2I5NghP7K-W8q02b4HsdDU)給出一種有效率的方法來減少(1.2)與(2.2.1.2)的時間複雜度，完成k-core演算法。
圖4.高效率k-core演算法。
8~12行 計算出所有節點的max degree為多少，
```c=
for (int v = 0; v < n; v++) {
d = 0;
vector<int>::iterator u;
//計算所有node的degree並存在Degree[v]中
for (u = adj[v].begin(); u != adj[v].end(); ++u) {
d++;
}
Degree[v] = d;
if (d > md) { md = d; }
}
```
13~27行 有了max degree後就可以用counting sort完成一開始(1.2)的排序，時間複雜度為O(n)。
```c=
//宣告一個array:bin 存degree = index的點有幾個
int* bin = new int[md + 1];
for (int d = 0; d <= md; d++) {
bin[d] = 0;
}
for (int v = 0; v < n; v++) {
bin[Degree[v]]++;
}
//用counting sort排序，bin[i]紀錄degree為i的節點應在vert[]第幾個位置排起
//pos[i]紀錄ID為i的節點在vert[]的第幾個位置，vert[i]紀錄第i個位置的節點的ID。
start = 0;
for (int d = 0; d < md + 1; d++) {
num = bin[d];
bin[d] = start;
start = start + num;
}
//使用bin[]幫忙計算節點的位置。
for (int v = 0; v < n; v++) {
pos[v] = bin[Degree[v]];
vert[pos[v]] = v;
bin[Degree[v]]++;
}
//還原bin[]的值
for (int d = md; d >= 1; d--) {
bin[d] = bin[d - 1];
}
bin[0] = 0;
```
圖5.各種陣列的關係
28~41行 原本圖3中挑完節點u之後Vert要重新依照degree做排序，實際上只要做一次交換就可以完成排序。
```c=
for (int i = 0; i < n; i++) {
v = vert[i];
vector<int>::iterator u;
for (u = adj[v].begin(); u != adj[v].end(); ++u) {
if (Degree[*u] > Degree[v]) {
//交換節點u與節點w
//節點w是在矩陣Vert[]中第一個與節點u有一樣degree的節點
int pu, du, pw, w;
du = Degree[*u];
pu = pos[*u];
pw = bin[du];
w = vert[pw];
if (*u != w) {
pos[*u] = pw;
vert[pu] = w;
pos[w] = pu;
vert[pw] = *u;
}
bin[du]++;
Degree[*u]--;
}
}
}
```
圖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](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm)
```
algorithm BronKerbosch1(R, P, X) is
if P and X are both empty then
report R as a maximal clique
for each vertex v in P do
BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}
```
此演算法採用窮舉所有可能的子圖(當然可以找到解)。時間複雜度 O(n⋅3ⁿᐟ³)。
此算法枚舉了大量不是Maximum Clique的集合，浪費許多時間。
我觀察演算法，發現到一開始就挑到對的節點，後面不是答案的窮舉就可以用[Branch and bound](https://en.wikipedia.org/wiki/Branch_and_bound)省略。
那要怎麼樣找到對的節點呢?
於是我就想到了可以用coreness先將節點做排序，節點coreness為k代表至少該節點有一個subgraph內所有節點都至少是k degree。一個Maximum Clique內若有n個節點，則所有節點的coreness至少都為n，(相反不一定成立，n core subgraph不一定是clique)，所以優先挑選coreness最大的節點，會最有可能找到Maximum Clique。
```c=
//Q為已經挑選的節點的集合 ， R為可以挑選的節點的集合已經按照coreness小到大排序
void get_max_clique(vector<Rnode> R, vector<Rnode> Q) {
//若找到的集合Q>已知的最大Clique集合，更新已知的最大Clique集合
if (Q.size() > curmax) {
Qmax = Q;
curmax = Qmax.size();
}
if (R.size() > 0) {
vector<Rnode> newR;
Rnode u;
int maxcoreness;
while (!R.empty()) {
maxcoreness = count_max_coreness(R);
//branch and bound
//若R集合中的節點coreness都不大於curmax，則不必再計算，
if (maxcoreness + 1 > curmax) {
//pick a node which has max coreness in set R
u = R.back();
newR.clear();
Q.push_back(u);
vector<Rnode>::iterator a;
for (a = R.begin(); a != R.end(); ++a) {
if (connected(a->id, u.id)) {
newR.push_back(*a);
}
}
get_max_clique(newR, Q);
Q.pop_back();
R.pop_back();
//}
}
else return;
}
}
return;
}
```
後來順利在時間內完成。
## 論文參考
寫這篇文章的當下發現說使用coreness與[Bron–Kerbosch algorithm](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm)中的提到
With vertex ordering是一樣的方法，
degeneracy的定義:
>In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.
>
與coreness定義不同但結果相同。
Bron–Kerbosch with degeneracy演算法時間負責度為O(dn^(3d/3))，d為coreness(degeneracy)。
我的演算法結合了[Branch and bound](https://en.wikipedia.org/wiki/Branch_and_bound)與Bron–Kerbosch with degeneracy，與論文[Fast Maximum Clique Algorithms for Large Graphs](https://www.cs.purdue.edu/homes/dgleich/publications/Rossi%202014%20-%20max-clique.pdf)有相似的psuedo-code
該論文表示在真實世界的網路中執行時間在log scale下有接近線性時間。
完整的code:
```c=
#include <iostream>
#include<vector>
#include<list>
#include<set>
#include <algorithm>
#include<signal.h>
#include<fstream>
#include<string>
#define publicEdge 2925046
#define privateEdge 2110828
#define publicvertices 82168
#include<time.h>
using namespace std;
vector<int> adj[82168];
int coreness[82168];
bool connected(int i, int j);
int curmax;
int max_v = 0;
struct Rnode {
int id;
int degree;
int core;
};
vector<Rnode>Q;
vector<Rnode> Qmax;
struct Result {
int id;
int color;
};
bool compareBydegree(const Rnode& a, const Rnode& b)
{
return a.degree < b.degree;
}
bool compareBycore(const Rnode& a, const Rnode& b)
{
return a.core < b.core;
}
bool compareByid(const Rnode& a, const Rnode& b)
{
return a.id < b.id;
}
bool comp(const int& num1, const int& num2) {
return num1 > num2;
}
void signalHandler(int signum) {
//cout << "Get signal " << signum << endl;
//cout << "MAXQ: " << endl;
sort(Qmax.begin(), Qmax.end(), compareByid);
vector<Rnode>::iterator c;
fstream out;
out.open("clique.txt", ios::out);
for (c = Qmax.begin(); c != Qmax.end(); ++c) {
out << c->id << endl;
}
out.close();
exit(signum);
}
// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v, int Degree[])
{
Degree[u]++;
Degree[v]++;
adj[u].push_back(v);
adj[v].push_back(u);
}
void printGraph(vector<int > adj[], int V)
{
int v;
vector<int>::iterator h;
for (int u = 0; u < V; u++)
{
cout << "Node " << u << " makes an edge with \n";
for (h = adj[u].begin(); h != adj[u].end(); h++)
{
v = *h;
cout << "\tNode " << v << " with edge";
}
cout << "\n";
}
}
void kcore(int k) {
int* Degree = new int[max_v];
int n = max_v;
int* vert = new int[max_v];
int* pos = new int[max_v];
int md = 0; //maxdegree
int d = 0; //degree
int num;
int start;
fstream out2;
int v;
for (int v = 0; v < n; v++) {
d = 0;
vector<int>::iterator u;
//計算所有node的max degree並存在Degree[v]中
for (u = adj[v].begin(); u != adj[v].end(); ++u) {
d++;
}
Degree[v] = d;
if (d > md) { md = d; }
}
//宣告一個array:bin 存maxdegree = index的點有幾個
int* bin = new int[md + 1];
for (int d = 0; d <= md; d++) {
bin[d] = 0;
}
for (int v = 0; v < n; v++) {
bin[Degree[v]]++;
}
start = 0;
for (int d = 0; d < md + 1; d++) {
num = bin[d];
bin[d] = start;
start = start + num;
}
for (int v = 0; v < n; v++) {
pos[v] = bin[Degree[v]];
vert[pos[v]] = v;
bin[Degree[v]]++;
}
for (int d = md; d >= 1; d--) {
bin[d] = bin[d - 1];
}
bin[0] = 0;
for (int i = 0; i < n; i++) {
v = vert[i];
vector<int>::iterator u;
for (u = adj[v].begin(); u != adj[v].end(); ++u) {
if (Degree[*u] > Degree[v]) {
//交換節點u與節點w
//節點w是在矩陣Vert[]中第一個與節點u有一樣degree的節點
int pu, du, pw, w;
du = Degree[*u];
pu = pos[*u];
pw = bin[du];
w = vert[pw];
if (*u != w) {
pos[*u] = pw;
vert[pu] = w;
pos[w] = pu;
vert[pw] = *u;
}
bin[du]++;
Degree[*u]--;
}
}
}
out2.open("kcore.txt", ios::out);
for (int i = 0; i < max_v; i++) {
if (Degree[i] >= k) {
out2 << i << " " << Degree[i] << endl;
}
coreness[i] = Degree[i];
}
out2.close();
}
bool connected(int i, int j) {
vector<int>::iterator a;
for (a = adj[i].begin(); a != adj[i].end(); ++a) {
if (*a == j)
return true;
}
return false;
}
int count_max_coreness(vector<Rnode> R) {
vector<Rnode>::iterator a;
int maxcoreness = 0;
for (a = R.begin(); a != R.end(); ++a) {
if (coreness[a->id] > maxcoreness) {
maxcoreness = coreness[a->id];
}
}
return maxcoreness;
}
void get_max_clique(vector<Rnode> R, vector<Rnode> Q) {
if (Q.size() > curmax) {
Qmax = Q;
curmax = Qmax.size();
}
if (R.size() > 0) {
vector<Rnode> newR;
Rnode u;
int maxcoreness;
while (!R.empty()) {
maxcoreness = count_max_coreness(R);
//branch and bound
//curmax是節點數量 coreness是Degree故需加一
if (maxcoreness + 1 > curmax) {
//pick a node which has max coreness in set R
u = R.back();
newR.clear();
Q.push_back(u);
vector<Rnode>::iterator a;
for (a = R.begin(); a != R.end(); ++a) {
if (connected(a->id, u.id)) {
newR.push_back(*a);
}
}
get_max_clique(newR, Q);
Q.pop_back();
R.pop_back();
//}
}
else return;
}
}
return;
}
int main(int argc, char* argv[])
{
fstream out3;
signal(SIGINT, signalHandler);
double START, END;
START = clock();
string file_name = string(argv[1]);
string K = string(argv[2]);
int k = stoi(K);
int Degree[82168];
int V = 82168;
vector<Rnode> R;
ifstream in;
in.open(file_name);
int a, b;
while (in >> a >> b) {
addEdge(adj, a, b, Degree);
if (b > max_v) {
max_v = b;
}
}
in.close();
//初始化R
Rnode Relement;
max_v++;
for (int i = 0; i < max_v; i++) {
Relement.degree = Degree[i];
Relement.id = i;
R.push_back(Relement);
}
kcore(k);
vector<Rnode>::iterator e;
for (e = R.begin(); e != R.end(); ++e) {
//cout<<" e id:"<<e->id;
e->core = coreness[e->id];
}
out3.open("clique.txt", ios::out);
sort(R.begin(), R.end(), compareBycore);
get_max_clique(R, Q);
//cout << "MAXQ: " << endl;
sort(Qmax.begin(), Qmax.end(), compareByid);
vector<Rnode>::iterator c;
for (c = Qmax.begin(); c != Qmax.end(); ++c) {
out3 << c->id << endl;
}
out3.close();
cout << endl;
END = clock();
//cout << "Execution time:" << (END - START) / CLOCKS_PER_SEC << " sec" << endl;
}
```
## 還可以改善的地方
在`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()降低時間複雜度。
Google Drive
Gist
Clipboard
Sign in with Wallet
