graph_kernels_labeled.py 文件源码

def graphlet_kernel(g1, g2=None):
    with Timer("Graphlet Kernel"):
        if g2 is not None:
            graphs = []
            for g in g1:
                graphs.append(g)
            for g in g2:
                graphs.append(g)
        else:
            graphs = g1

        N = len(graphs)

        graphlet_counts = []
        graphlets = {}

        ind = 0
        for i in range(len(graphs)):
            d = {}
            for node1 in graphs[i].nodes():
                for node2 in graphs[i].neighbors(node1):
                    for node3 in graphs[i].neighbors(node2):
                        if node1 != node3:
                            if node3 not in graphs[i].neighbors(node1):
                                graphlet = (1, min(graphs[i].node[node1]['label'], graphs[i].node[node3]['label']),
                                            graphs[i].node[node2]['label'],
                                            max(graphs[i].node[node1]['label'], graphs[i].node[node3]['label']))
                                if graphlet not in graphlets:
                                    graphlets[graphlet] = len(graphlets)
                                if graphlets[graphlet] in d:
                                    d[graphlets[graphlet]] += 1.0 / 2.0
                                else:
                                    d[graphlets[graphlet]] = 1.0 / 2.0
                            else:
                                labs = sorted([graphs[i].node[node1]['label'], graphs[i].node[node2]['label'],
                                               graphs[i].node[node3]['label']])
                                graphlet = (2, labs[0], labs[1], labs[2])
                                if graphlet not in graphlets:
                                    graphlets[graphlet] = len(graphlets)
                                if graphlets[graphlet] in d:
                                    d[graphlets[graphlet]] += 1.0 / 6.0
                                else:
                                    d[graphlets[graphlet]] = 1.0 / 6.0

            graphlet_counts.append(d)

        phi = lil_matrix((N, len(graphlets)))
        for i in range(len(graphs)):
            for graphlet in graphlet_counts[i]:
                phi[i, graphlet] = graphlet_counts[i][graphlet]

        if g2 is not None:
            K = np.dot(phi[:len(g1), :], phi[len(g1):, :].T)
        else:
            K = np.dot(phi, phi.T)

        K = np.asarray(K.todense())
        return K


# Compute Weisfeiler-Lehman subtree kernel