ALGORITHM SCAN(G=<V, E>, ε, μ)

// all vertices in V are labeled as unclassified;

for each unclassified vertex v ∈ V do

// STEP 1. check whether v is a core;

    if COREε,μ(v) then

// STEP 2.1. if v is a core, a new cluster is expanded;

        generate new clusterID;

        insert all x ∈ Nε (v) into queue Q;

        while Q ≠  do

            y = first vertex in Q;

            R = {x ∈ V | DirREACHε,μ(y, x)};

            for each x ∈ R do

                if x is unclassified or non-member then

                    assign current clusterID to x;

                if x is unclassified then

                    insert x into queue Q;

            remove y from Q;

    else

// STEP 2.2. if v is not a core, it is labeled as non-member

        label v as non-member;

end for.

// STEP 3. further classifies non-members

for each non-member vertex v do

    if (∃ x, y ∈ Γ(v) ( x.clusterID ≠ y.clusterID) then

        label v as hub

    else

        label v as outlier;

end for.

end SCAN.

"""Find k-clique communities in graph using the percolation method.

A k-clique community is the union of all cliques of size k that can be reached through adjacent (sharing k-1 nodes) k-cliques.
Parameters:

    k (int) – Size of smallest clique
    cliques (list or generator) – Precomputed cliques (use networkx.find_cliques(G))

Return type:

Yields sets of nodes, one for each k-clique community.

"""
import networkx as nx

import sys

import time

def find_community(graph,k):

    return list(nx.k_clique_communities(graph,k))

G = nx.Graph()

##testFile=open("F://2.txt","r") ##2-6

testFile=open("F://21.txt","r") ##5,10

for line in testFile:

    a=line.strip('\n').split(",")

    G.add_edge(a[0],a[1])

for k in range(5,10):

        print ("############# k值: %d ################" % k)

        start_time = time.clock()

        rst_com = find_community(G,k)

        end_time = time.clock()

        print ("计算耗时(秒)：%.3f" % (end_time-start_time))

        print ("生成的社区数：%d" % len(rst_com))

        print(rst_com)

a,b

c,d

a,c

a,d