计算紧密中心性(C语言实现)
时间: 2023-09-12 10:07:51 浏览: 41
紧密中心性是用于衡量节点在图中的重要性的指标,它是指节点与其他节点之间最短路径的平均长度的倒数。
下面是一个简单的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF INT_MAX
#define N 5
int graph[N][N] = {
{0, 1, INF, 1, INF},
{1, 0, 1, INF, INF},
{INF, 1, 0, 1, INF},
{1, INF, 1, 0, 1},
{INF, INF, INF, 1, 0}
};
double closeness_centrality(int node) {
int i, j, sum = 0, shortest_path, reachable_count = 0;
double closeness;
int dist[N] = { 0 };
for (i = 0; i < N; i++) {
dist[i] = INF;
}
dist[node] = 0;
for (i = 0; i < N; i++) {
shortest_path = INF;
for (j = 0; j < N; j++) {
if (dist[j] < shortest_path && dist[j] != -1) {
shortest_path = dist[j];
node = j;
}
}
for (j = 0; j < N; j++) {
if (graph[node][j] > 0 && dist[node] + graph[node][j] < dist[j]) {
dist[j] = dist[node] + graph[node][j];
}
}
dist[node] = -1;
}
for (i = 0; i < N; i++) {
if (dist[i] != INF && i != node) {
sum += dist[i];
reachable_count++;
}
}
closeness = (double)(reachable_count - 1) / sum;
return closeness;
}
int main() {
int i;
double cc[N];
for (i = 0; i < N; i++) {
cc[i] = closeness_centrality(i);
printf("Node %d has closeness centrality: %f\n", i, cc[i]);
}
return 0;
}
```
这个示例程序计算了一个大小为 5 的图的紧密中心性,其中每个节点都被编号为 0 到 4。图的邻接矩阵被硬编码到程序中,其中 INF 表示两个节点之间没有边。该程序输出每个节点的紧密中心性。