2-3 社交网络图中结点的“重要性”计算

2-3 社交网络图中结点的“重要性”计算

分数 25
作者 DS课程组
单位 浙江大学

在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。

“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有N个结点的网络中，结点vi​的“紧密度中心性”Cc(vi​)数学上定义为vi​到其余所有结点vj​ (j≠i) 的最短距离d(vi​,vj​)的平均值的倒数：

对于非连通图，所有结点的紧密度中心性都是0。

给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。
输入格式:

输入第一行给出两个正整数N和M，其中N（≤10^4）是图中结点个数，顺便假设结点从1到N编号；M（≤10 ^5）是边的条数。随后的M行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K（≤100）以及K个结点编号，用空格分隔。
输出格式:

按照Cc(i)=x.xx的格式输出K个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后2位。

输入样例:

9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出样例:

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35
1
2
3

代码长度限制
16 KB
时间限制
20000 ms
内存限制
64 MB
C++ (g++)

思路：

求从任一顶点到其余顶点的最短距离，即多源顶点间的距离。可以用弗洛伊德算法求解。

使用Floyd算法，求多源最短路径。vi和每个结点的最短距离之和，即让我们求任意两点之间的最短路径。

Floyd算法:

Floyd
当计算i到j之间的最短距离时，利用一个过渡顶点k，先求出i和k之间的距离，再加上k和j之间的距离，对比得出最短距离（动态规划思想）。图中任意两顶点间都通过过渡顶点计算。
floyd算法需要维护两个二维数组：（i和j均为顶点数组的索引）

distance[i][j]: 保存第i个顶点和第j个顶点的最短距离。初始时为图的邻接数组值。
prePath[i][j]: 保存第i个顶点到第j个顶点的前驱结点值。
1
2

算法分析：
floyd算法中有三次for，最外层为过渡结点，中间层为顶点，最内层为终点，算法复杂度为O（n^3).对于稠密图求解最佳，运行依次便可得出所以顶点之间的关系

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(graph[i][j]>graph[i][k]+graph[k][j])
                    graph[i][j]=graph[i][k]+graph[k][j];
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11

AC代码：

#include
using namespace std;

const int inf=65535;
int graph[10001][10001];
int n,m;

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(graph[i][j]>graph[i][k]+graph[k][j])
                    graph[i][j]=graph[i][k]+graph[k][j];
            }
        }
    }
}

void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)
                graph[i][j]=0;
            else 
                graph[i][j]=inf;
        }
    }
}

int main()
{
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        int t1,t2;
        cin>>t1>>t2;
        graph[t1][t2]=graph[t2][t1]=1;
    }
    floyd();
    bool flag=true;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(graph[i][j]==inf){//不连通
                flag=false;
                break;
            }
        }
    }
    int k,id;
    cin>>k;
    while(k--){
        cin>>id;
        if(!flag)
            printf("Cc(%d)=0.00\n",id);
        else{
            int dis=0;
            for(int i=1;i<=n;i++){
                dis+=graph[id][i];
            }
            printf("Cc(%d)=%.2lf\n",id,(n-1)*1.0/dis);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64