changed 3 years ago  
Published Linked with GitHub

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這篇論文
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為多少，











    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)。































//宣告一個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做排序，實際上只要做一次交換就可以完成排序。
























   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

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省略。
那要怎麼樣找到對的節點呢?
於是我就想到了可以用coreness先將節點做排序，節點coreness為k代表至少該節點有一個subgraph內所有節點都至少是k degree。一個Maximum Clique內若有n個節點，則所有節點的coreness至少都為n，(相反不一定成立，n core subgraph不一定是clique)，所以優先挑選coreness最大的節點，會最有可能找到Maximum Clique。








































//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中的提到
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與Bron–Kerbosch with degeneracy，與論文Fast Maximum Clique Algorithms for Large Graphs有相似的psuedo-code

該論文表示在真實世界的網路中執行時間在log scale下有接近線性時間。

完整的code:






























































































































































































































































































#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()降低時間複雜度。

Select a repo