communitystructuredetectingofcomplexnetwork(realizethegnalgorithmbyjavacode).txt

复杂网络社团结构的发现

} //class


class Modularity {
    Static int flagvalue[];
    int flagvaluestate[] = new int[40];
    Static int flag[];
    Static int count;
    Static int commu_member[][]; //\u8BB0\u5F55\u6BCF\u4E2A\u793E\u56E2\u7640\u6210\u5458
    Static int temp[];
    Static int k[]; //k[i]\u4068\u793A\u7B2Ci\u4E2A\u793E\u56E2\u7640\u4EBA\u6570
    int edgepoint1, edgepoint2;
    int commu_memberstate[][];
    int countstate;
    int kstate[];
    Static int T = 0;
    int checkvalue = 0;
    int Ti = 0;
    float Q = 0;
    float Qw;
    int v1, v2;
    Static int a = 0;
    float return_Qw() {
        return Qw;
    }

    Static void initial() {
        temp = new int[40];
        flagvalue = new int[40];
        flag = new int[40];
        k = new int[40];

        for (int i = 0; i < 40; i++) {
            flagvalue[i] = i;
            flag[i] = 0;
            k[i] = 0;
            temp[i] = -1;
        }
        for (int i = 0; i < 40; i++) {
            for (int j = 0; j < 40; j++) {
                T = T + Progress.num1[i][j];
            }
        }

    }

    int check(int m, int n) {
        if (flagvaluestate[m] == flagvaluestate[n]) {
            checkvalue = 1;
            return 1;
        } else {
            checkvalue = 0;
            return 0;
        }

    }

    int calcu_Ti(int m) {
        for (int n = 0; n < 40; n++) {
            Ti += Progress.num1[m][n];
        }
        return Ti;
    }


    float calculate_Qw() {
        for (int i = 0; i < 40; i++) {
            for (int j = 0; j < 40; j++) { // if(i!=j)
                Q +=
                        (Progress.num1[i][j] -
                         (calcu_Ti(i) * calcu_Ti(j)) / (2 * T)) *
                        check(i, j);

            }
        }
        Qw = Q / (2 * T);
        return Qw;
    }

    void addedge(int m, int n, Modularity A) {
        v1 = flagvalue[m];
        v2 = flagvalue[n];
        if (flag[n] == 1 && flag[m] == 0) {
            flagvalue[m] = flagvalue[n];
            flag[m] = 1;
        } else if (flag[m] == 1 && flag[n] == 0) {
            flagvalue[n] = flagvalue[m];
            flag[n] = 1;
        } else if (flag[m] == 0 && flag[n] == 0) {
            flagvalue[m] = flagvalue[n];
            flag[m] = flag[n] = 1;
        } else if (flag[m] == 1 && flag[n] == 1) {

            /* for(int i=0;i<40;i++)
             {    if(flagvalue[i]==flagvalue[n])
                 {
                     flagvalue[i] = flagvalue[m] ;

                 }
             }//for
             */
            for (int i = 0; i < A.countst(); i++) {
                for (int j = 0; j < A.re_kstate(i); j++) {
                    if (A.commu_memberstate[i][j] == m) {
                        for (int z = 0; z < A.re_kstate(i); z++) {
                            flagvalue[A.commu_memberstate[i][z]] = flagvalue[n];
                        }
                    }
                }
            }
        }
        //a++;
        //flag[m]=flag[n]=1;
        for (int i = 0; i < 40; i++) {
            flagvaluestate[i] = flagvalue[i];
        }
    } //addedge

    void modul_num() {
        int i, j, flagg = 0;
        count = 1;
        temp[0] = flagvalue[0];
        for (i = 1; i < 40; i++) {
            flagg = 0;
            for (j = 0; j < count; j++) {
                if (flagvalue[i] == temp[j]) {
                    flagg = 1;
                    break;
                }
            }
            if (flagg == 0) {
                temp[count] = flagvalue[i];
                count++;
            }
        }
        //count=count+1;
    } //modul_num

    void com_mem() {
        k = new int[count];
        for (int i = 0; i < count; i++) {
            k[i] = 0;
        }
        commu_member = new int[count][40];
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < 40; j++) {
                commu_member[i][j] = -1;
            }
        }
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < 40; j++) {
                if (temp[i] == flagvalue[j]) {
                    commu_member[i][k[i]++] = j;
                }
            }

        }
    } //com_mem()

    void evaluate(int m, int n) {
        commu_memberstate = new int[count][40];
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < 40; j++) {
                commu_memberstate[i][j] = -1;
            }
        }

        kstate = new int[count];
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < k[i]; j++) {
                commu_memberstate[i][j] = commu_member[i][j];
            }
        }
        edgepoint1 = m;
        edgepoint2 = n;
        countstate = count;
        for (int i = 0; i < countstate; i++) {
            kstate[i] = k[i];
        }

    }

    void print_outcome() {
        System.out.println("\u5171" + countstate + "\u4E2A\u793E\u56E2:");

        for (int i = 0; i < countstate; i++) { //System.out.println("\u7B2C"+(i+1)+"\u4E2A\u793E\u56E2\u7640\u6210\u5458\u4E2A\u6570\u662F"+kstate[i]);
            System.out.print("\u7B2C" + (i + 1) +
                             "\\u4E2A\u793E\u56E2\u7640\u793E\u56E2\u6210\u5458\u662F:");
            for (int j = 0; j < kstate[i]; j++) {
                System.out.print(commu_memberstate[i][j]);
                System.out.print("   ");
            }
            System.out.println();
        }
    }

    int point1() {
        return edgepoint1;
    }

    int point2() {
        return edgepoint2;
    }

    int countst() {
        return countstate;
    }

    int re_kstate(int i) {
        return kstate[i];
    }
} //class Modularity


class Mainn {
    public Static void main(String args[]) {
        Progress A = new Progress();
        A.pro(40);
        int savepoint[] = new int[20000];
        int countsavepoint = 0;
        float qq[]=new float[40];
        int f=0;
        int edgew[][] = new int[40][40];
        int edgebig;
        int flagm = 0;
        int flagn = 0, flagf;
        int count = 0;
        for (int i = 0; i < 1000; i++) {
            savepoint[i] = -1;
        }
        System.out.println("边介数：");
        while (true) {
            edgebig = 0;
            flagf = 0;
            for (int m = 0; m < 40; m++)
                for (int n = 0; n < 40; n++)
                    edgew[m][n] = 0;



            for (int i = 0; i < 40; i++) {
                A.shortest_path(40, i);
                A.distAndweight(i, 40);
                A.createshortree(i, 40);
                A.findleave(i, 40);
                A.bubblesort(A.d, 40);
                A.calculate(40);

                for (int m = 0; m < 40; m++)
                    for (int n = 0; n < 40; n++)
                        edgew[m][n] += A.edgeweight[m][n];


            }//for
            /* for (int m = 0; m < 40; m++) {
                 for (int n = 0; n < 40; n++) {
                    System.out.print(edgew[m][n]);

                     if (edgew[m][n] < 10)
                         System.out.print("    ");
                     else if (edgew[m][n] >= 10 && edgew[m][n] < 100)
                         System.out.print("   ");
                     else if (edgew[m][n] >= 100 && edgew[m][n] < 1000)
                        System.out.print("  ");

                 }
                 System.out.println();
             }
             */

           /*for (int m = 0; m < 40; m++)
                for (int n = 0; n < 40; n++)
                   if (A.num1[m][n] != 0)
                        edgew[m][n] = edgew[m][n] / A.num1[m][n];
           */



            int m = 0, n = 0;
            for (m = 0; m < 40; m++)
                for (n = 0; n < 40; n++)
                    if (edgew[m][n] > edgebig) {
                        edgebig = edgew[m][n];
                        flagm = m;
                        flagn = n;
                    }



            savepoint[countsavepoint] = flagm;
            countsavepoint++;
           savepoint[countsavepoint] = flagn;
           countsavepoint++;
           A.num[flagm][flagn] = 0;
           A.num[flagn][flagm] = 0;

            System.out.print(flagm);
            System.out.print("   ");
            System.out.print(flagn);
             System.out.print("        ");
             System.out.println(" ");


           /*  for (m = 0; m < 40; m++)
               for (n = 0; n < 40; n++)
                    if (edgew[m][n] == edgebig) {
                       flagm = m;
                       flagn = n;
                    savepoint[countsavepoint++] = flagm;
                    savepoint[countsavepoint++] = flagn;
            // System.out.print(flagm);
            // System.out.print("   ");
            // System.out.print(flagn);
            // System.out.print("        ");
            // System.out.println(" ");

               A.num[flagm][flagn] = 0;
               A.num[flagn][flagm] = 0;
             }//if
        */
            //System.out.println(edgebig);

            count++;

            //System.out.println(edgebig);

            for (m = 0; m < 40; m++)
                for (n = 0; n < 40; n++)
                    if (A.num[m][n] != 0)
                        flagf = 1;



            if (flagf == 0) {
                break;
            }
        } //while(1)
        int count2 = countsavepoint;
        System.out.println(count);
        int point1 = 0, point2 = 0;
        Modularity B[];
        B = new Modularity[count2];
        //for(int i=0;i<count;i++)
        //B[i]=new Modularity();


        float calcuQ;
        Modularity.initial();
        int i = 0;
        float Qmax = -100;
        int flagi = -1;
        int count1 = 0;
        while (countsavepoint != 0) {
            countsavepoint--;
            point1 = savepoint[countsavepoint];
            countsavepoint--;
            point2 = savepoint[countsavepoint];
            // System.out.print("point1:");
            // System.out.println(point1);
            //System.out.print("point2:");
            //System.out.println(point2);

            // if(!(B[i].flag[point1]==1&&B[i].flag[point2]==1))
            //{
            B[i] = new Modularity();
            if (i == 0) {
                B[i].addedge(point1, point2, B[0]);
            }
            if (i > 0)
            B[i].addedge(point1, point2, B[i - 1]);
            B[i].modul_num();
            B[i].com_mem();
            B[i].evaluate(point1, point2);
            B[i].calculate_Qw();
            if (i > 0 && B[i].count < B[i - 1].countst()) {
                B[i].print_outcome();
                 qq[f++]=B[i].return_Qw();
                //System.out.println(B[i].return_Qw());
                count1++;
            }
            calcuQ = B[i].return_Qw();
            if (calcuQ > Qmax) {
                Qmax = calcuQ;
                flagi = i;
            }

            i++;
            //}//if
        } //while
        for( i=f-1;i>=0;i--)
            System.out.println(qq[i]);
        //System.out.println("count1:" + count1);
        //System.out.println("Qw\u7640\u6700\u5927\u503C\u4E3A:");
        //System.out.println(Qmax);
        //System.out.println("\u8FD9\u65F6\u7640\u793E\u56E2\u7ED3\u6740\u662F:");
        //B[flagi].print_outcome();

    } //main

} //class