C++计算简单图得聚集系数和邻里重叠度

计算聚集系数和邻里重叠度
输入：任意图的邻接矩阵
输出：

• 1）每个节点的聚集系数
• 2）每个节点对的邻里重叠度

思路

1.求聚集系数 Cluster Coefficient

一个节点的聚类参数被称为 Local Cluster Coefficient。它的计算方法也是非常的简单粗暴。先计算所有与当前节点连接的节点中间可能构成的 link 有多少个，这个数会作为分母，然后计算实际上有多少个节点被连接上了，这个数会作为分子。最终的计算结果就是 Local Cluster Coefficient。

上图中的节点 C 的 Local Cluster Coefficient 就是 1⁄3。

2.求邻里重叠度

邻里重叠度是一个已有网络用来描述某一条边的属性的量。
它通过定义(A, B)边的“与A、B均为邻居的节点数”与“与A、B中至少一个为邻居的节点数”的比值来描述一条边是否具有“捷径” 的特性。
定义：与A、B均为邻居的节点数/ 与节点A、B中至少一个为邻居的节点数

代码

求每个顶点的聚集系数：其中graph是图结构，用于储存邻接矩阵。

    string aggCoeff[n+1];//记录每个顶点的聚集系数
    for (int k = 1; k <= n; ++k) {
        int my_degree = 0;

        my_degree = graph.degree(k);
//cout<<"度为"<<my_degree<<endl;cout<<endl;
        int denominator = my_degree*(my_degree-1)/2;
        if (denominator==0){
            aggCoeff[k]="0";
        } else{
            int molecule = graph.getFriendsIsFriends(k);
//cout<<"分子是："<<molecule<<endl;
            if(molecule==0){
                aggCoeff[k]="0";
            } else{
                int temp=molecule/denominator;
                if(temp==1){
                    aggCoeff[k]="1";
                } else{
                    aggCoeff[k]=to_string(molecule)+"/"+to_string(denominator);
                }
            }
        }
    }
    for (int l = 1; l <= n; ++l) {
        cout<<"顶点"<<l<<"的聚集系数为："<<aggCoeff[l]<<endl;
    }

    //返回A的任意两个朋友之间也是朋友数目
    int getFriendsIsFriends(int iE) {

        int *friends = new int[degree(iE)];
        int start = 0;
        for (int j = 1; j <= this->n; ++j) {
            if (this->existsEdge(iE, j)) {
                friends[start++] = j;
//cout<<"邻接的顶点是："<<j<<endl;
            }
        }

        int friendsIsFriends = 0;
        //检查朋友之间是否为朋友
        for (int i = 0; i < degree(iE); i++) {
            //检查这一行的值
            for (int k = 0; k < degree(iE) - 1 - i; k++) {

                int a = friends[i];
                int b = friends[i + 1 + k];
                if (this->existsEdge(a, b)) {
                    friendsIsFriends++;
                }
            }
        }
        return friendsIsFriends;

    }

求每条边的邻里重叠度,其中getDeno方法是获取与A或B邻接的定点数，getCoin是获取与A和B邻接的顶点数。

//记录每对相邻节点的邻里重叠度
    string *degreeEdges = new string[e];
    int start2 = 0;
    for (int m = 1; m < n ; ++m) {
        for (int i = m+1; i <=n ; ++i) {
            if (graph.existsEdge(m,i)){
                //获得与A，B邻接的顶点
                int *getAEdges = graph.getEdges(m);
                int *getBEdges = graph.getEdges(i);

                int legA = graph.degree(m);
                int legB = graph.degree(i);

                if(legA==1&&legB==1){
                    degreeEdges[start2++]="0";
                } else{
                    int denominator = getDeno(getAEdges,getBEdges,legA,legB);
                    int molecule = getCoin(getAEdges,getBEdges,legA,legB);

                    if(denominator==molecule){
                        degreeEdges[start2++]="1";
                    } else if(molecule==0){
                        degreeEdges[start2++]="0";
                    } else{
                        degreeEdges[start2++]=to_string(molecule)+"/"+to_string(denominator);
                    }
                }

                cout<<"边（"<<m<<","<<i<<"）之间的邻里重叠度为："<<degreeEdges[start2-1]<<endl;

            }
        }
    }
    //返回与顶点i邻接的顶点
    int *getEdges(int i) {
        int *my_result = new int[this->degree(i)];
//cout<<i<<"度为："<<this->degree(i)<<endl;
        int start = 0;
        for (int j = 1; j <= this->n ; ++j) {
            if (this->existsEdge(i,j)){
                my_result[start++] = j;
//                cout<<i<<"的临界点有"<<j<<endl;
            }
        }
//cout<<i<<"的相邻的定点有几个："<< sizeof(my_result) <<endl;//返回的是指针的大小
        return my_result;
    }