基于最短路径算法的社区发现算法-Gewman and Girvan算法)

重要概念

边介数（betweenness）：网络中任意两个节点通过此边的最短路径的数目。

GN算法的思想：在一个网络之中，通过社区内部的边的最短路径相对较少，而通过社区之间的边的最短路径的数目则相对较多。下图中展示了变得强度以及边介数在现实网络中的分布情况。GN算法是一个基于删除边的算法，本质是基于聚类中的分裂思想，在原理上是使用边介数作为相似度的度量方法。在GN算法中，每次都会选择边介数高的边删除，进而网络分裂速度远快于随机删除边时的网络分裂。

GN算法的步骤如下：
（1）计算每一条边的边介数；
（2）删除边界数最大的边；
（3）重新计算网络中剩下的边的边阶数；
（4）重复(3)和(4)步骤，直到网络中的任一顶点作为一个社区为止。

GN算法示例：

实现想法：
（1）用最短路径算法求出任意两点间的最短路径
（2）借用最短路径算出每条边的边介数，也就是创建一个节点数*节点数的二维矩阵，然后只要有最短路径通过某条边，此边的二维矩阵中的边介数加1
（3）遍历整个边介数矩阵，找出最大的边介数的边的值
（4）将所有等于此边介数的边的值赋值为无穷大（也就是断开这条边）
（5）找出所有的社团，并计算模块系数Q
（6）如果模块系数Q大于某个q值（一般在0.3到0.7之间），结束算法，输出所有的社团，否则从（1）再次执行
代码：
最短路径算法人尽皆知，不再展示，算出的最短路径存储在一个二维的AarryList或者二维的Stack中均可。

					//求出各边的边介数,Stack中存储的是最短路径
                    while (stack.size() > 1) {
                        int q = stack.pop();
                        int b = stack.peek();
                        edge[q][b]++;
                        edge[b][q]++;
                    }
                    stack.pop();

 		//找出最大边介数
        for (int q = 0; q < edge.length; q++) {
            for (int b = 0; b < edge.length; b++) {
                if (temp < edge[q][b]) temp = edge[q][b];
            }
        }

        //将边介数最大的边的权值设为无穷大
        for (int q = 0; q < edge.length; q++) {
            for (int b = 0; b < edge.length; b++) {
                if (temp == edge[q][b]) {
                    graph.edges[q][b] = INF;
                    graph.edges[q][b] = INF;
                }
            }
        }//endfor

找出社团比较麻烦，用广度优先搜索或者深度优先搜索找均可

	//深度优先遍历
	public static void DFS(int[][] graph, boolean[] visitied, int start, ArrayList<Integer> arrayList){
		for(int j = 0; j<graph.length; j++){
			if(graph[start][j] == 1 && !visitied[j]){
				visitied[j] = true;
				arrayList.add(j);
				DFS(graph, visitied, j, arrayList);
			}
			if(j == graph.length-1) return;
		}
	}

//广度优先算法遍历整个图
public class BFSfisrt {
	private Queue q;
	private Queue<Integer> visited;
	public BFSfisrt() {
		// TODO Auto-generated constructor stub
		q=new LinkedList();
		visited=new LinkedList<>();
	}
	
	private int getIndex(char v,char[] str)
	{
		for(int i=0;i<str.length;i++)
		{
			if(v==str[i])
				return i;
		}
		return -1;
	}
	
	
	
	public Stack<Integer> bfs(int[][] matrix, char v, char[] str, int vd[])
	{

		Stack<Integer> stack = new Stack<>();
		int i=getIndex(v,str);
		if(i==-1){
			System.out.println("error");
			return stack;
		}
		q.add(i);
		visited.add(i);
		System.out.print(str[i]+" ");
		stack.push(i);
		while(!q.isEmpty())
		{
			int u=(int)q.remove();
			
			for(int j=0;j<str.length;j++)
			{
				if(matrix[u][j]==1 && (!visited.contains(j)))
				{
					
					q.add(j);
					visited.add(j);
					stack.push(j);
				}
			}
		}
	return stack;
	}

}

再找出强连通分量，也就是分组

    //计算强连通分量
    public ArrayList<ArrayList<Integer>> SCCCount(){
        group = new ArrayList<>();
        boolean[] visited = new boolean[graph.length]; //判断结点是否遍历过
        for(int i  = 0; i<visited.length; i++) visited[i] = false;

        //进行深度优先遍历
        for(int i = 0; i< graph.length; i++){
            if(!visited[i]) {
                ArrayList<Integer> arrayList = new ArrayList<>();
                group.add(arrayList);
                DFS(graph, visited, i, arrayList);
            }
        }

        for(int i  = 0; i<visited.length; i++) visited[i] = false;

        for(ArrayList<Integer> a: group){
            for(int i: a){
                visited[i] = true;
            }
        }

        //所有剩下没加入的点都是单个结点，将其作为一个独立的组加入
        for(int i  = 0; i<visited.length; i++){
            if(visited[i] == false){
                ArrayList<Integer> arrayList = new ArrayList<>();
                arrayList.add(i);
                group.add(arrayList);
                }
            }
    return group;
    }

最后计算模块系数Q

    public double modelRateQ(double edgeCount, int[][] graph){
        group = SCCCount();
        double groupEdge = 0;  //组内边介数
        double rateQ = 0;   //模块系数Q

        for(ArrayList<Integer> al: group){
            double nodeRate = 0;
            for(int node: al){
                //只有一个点的组的组内边的和为0
                if(al.size() == 1){
                    for(int i = 0; i<graph.length; i++){
                        //计算所有与node点相连接的边的数量
                        if(graph[node][i] > 0) nodeRate++;
                    }
                    continue;
                }
                for(int i = 0; i<graph.length; i++){
                    //计算所有与node点相连接的边的数量
                    if(graph[node][i] > 0) nodeRate++;
                    //计算组内边数
                    if(graph[node][i] > 0 && al.indexOf(i) != -1)
                            groupEdge++;
                }//endfor
            }//endfor
            rateQ -= (nodeRate/(edgeCount * 2)) * (nodeRate/(edgeCount * 2));
        }
        groupEdge /= 2;
        rateQ += groupEdge/edgeCount;
        System.out.println(rateQ);
        return rateQ;
    }