betweeness centrality java 源码

以下是Java中计算Betweenness Centrality的示例代码：

import java.util.*;

public class BetweennessCentrality {
    private Map<Integer, List<Integer>> graph;
    private int[] shortestPathsCount;
    private double[] dependency;
    private int[] distance;

    public BetweennessCentrality(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
        shortestPathsCount = new int[graph.size()];
        dependency = new double[graph.size()];
        distance = new int[graph.size()];
    }

    public Map<Integer, Double> calculate() {
        Map<Integer, Double> betweennessCentrality = new HashMap<>();
        for (int s = 0; s < graph.size(); s++) {
            Stack<Integer> stack = new Stack<>();
            Queue<Integer> queue = new LinkedList<>();
            List<Integer>[] predecessors = new ArrayList[graph.size()];
            int[] sigma = new int[graph.size()];

            Arrays.fill(predecessors, null);
            Arrays.fill(distance, -1);
            distance[s] = 0;
            sigma[s] = 1;
            queue.add(s);

            while (!queue.isEmpty()) {
                int v = queue.poll();
                stack.push(v);
                for (int w : graph.get(v)) {
                    if (distance[w] < 0) {
                        distance[w] = distance[v] + 1;
                        queue.add(w);
                    }
                    if (distance[w] == distance[v] + 1) {
                        sigma[w] += sigma[v];
                        if (predecessors[w] == null) {
                            predecessors[w] = new ArrayList<>();
                        }
                        predecessors[w].add(v);
                    }
                }
            }

            Arrays.fill(dependency, 0);
            while (!stack.isEmpty()) {
                int w = stack.pop();
                if (predecessors[w] != null) {
                    for (int v : predecessors[w]) {
                        dependency[v] += ((double) sigma[v] / sigma[w]) * (1 + dependency[w]);
                    }
                }
                if (w != s) {
                    betweennessCentrality.put(w, betweennessCentrality.getOrDefault(w, 0.0) + dependency[w]);
                }
            }
        }

        for (int v : betweennessCentrality.keySet()) {
            betweennessCentrality.put(v, betweennessCentrality.get(v) / 2.0);
        }

        return betweennessCentrality;
    }
}

这个实现使用了广度优先搜索（BFS）来计算最短路径和sigma值，使用了栈来保存顺序并计算依赖关系和Betweenness Centrality。请注意，这个实现假定图是无向的，如果需要计算有向图的Betweenness Centrality，需要做一些修改。