Une mise-à-jour est prévue le 9 juillet entre 13:00 et 14:00. Le service sera inaccessible ou instable pendant cette période. Merci de votre compréhension.

vertex_edge_overlap.pyx 3.01 KB
Newer Older
Fize Jacques's avatar
Fize Jacques committed
1 2 3 4
# coding = utf-8

import numpy as np
cimport numpy as np
5
from .base cimport Base,intersection
Fize Jacques's avatar
Fize Jacques committed
6 7
from .graph cimport Graph
from cython.parallel cimport prange,parallel
8
from ..helpers.general import parsenx2graph
Fize Jacques's avatar
Fize Jacques committed
9

10
cdef class VertexEdgeOverlap(Base):
Fize Jacques's avatar
Fize Jacques committed
11 12 13 14 15 16 17 18

    """
    Vertex/Edge Overlap Algorithm
    presented in Web graph similarity for anomaly detection, Journal of Internet Services and Applications, 2008
    by P. Papadimitriou, A. Dasdan and H.Gracia-Molina

    Code Author : Jacques Fize
    """
19 20
    def __init__(self):
            Base.__init__(self,0,True)
Fize Jacques's avatar
Fize Jacques committed
21

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
    cpdef np.ndarray compare_old(self,list listgs, list selected):
        n = len(listgs)
        cdef np.ndarray comparison_matrix = np.zeros((n, n))
        cdef list inter_ver,inter_ed
        cdef int denom,i,j
        for i in range(n):
            for j in range(i,n):
                g1,g2 = listgs[i],listgs[j]
                f=self.isAccepted(g1,i,selected)
                if f:
                    inter_g= intersection(g1,g2)
                    denom=g1.number_of_nodes()+g2.number_of_nodes()+\
                        g1.number_of_edges()+g2.number_of_edges()
                    if denom == 0:
                        continue
                    comparison_matrix[i,j]=(2*(inter_g.number_of_nodes()
                                            +inter_g.number_of_edges()))/denom # Data = True --> For nx.MultiDiGraph
                comparison_matrix[j, i] = comparison_matrix[i, j]
        return comparison_matrix

42
    cpdef np.ndarray compare(self,list listgs, list selected):
Fize Jacques's avatar
Fize Jacques committed
43
        cdef int n = len(listgs)
44
        cdef list new_gs=parsenx2graph(listgs)
Fize Jacques's avatar
Fize Jacques committed
45
        cdef double[:,:] comparison_matrix = np.zeros((n, n))
46
        cdef int denom,i,j
Fize Jacques's avatar
Fize Jacques committed
47 48 49
        cdef long[:] n_nodes = np.array([g.size() for g in new_gs])
        cdef long[:] n_edges = np.array([g.density() for g in new_gs])

50
        cdef bint[:] selected_test = self.get_selected_array(selected,n)
Fize Jacques's avatar
Fize Jacques committed
51 52 53

        cdef double[:,:] intersect_len_nodes = np.zeros((n, n))
        cdef double[:,:] intersect_len_edges = np.zeros((n, n))
Fize Jacques's avatar
Fize Jacques committed
54 55
        for i in range(n):
            for j in range(i,n):
Fize Jacques's avatar
Fize Jacques committed
56 57 58 59 60 61
                intersect_len_nodes[i][j]=new_gs[i].size_node_intersect(new_gs[j])
                intersect_len_edges[i][j]=new_gs[i].size_edge_intersect(new_gs[j])#len(set(hash_edges[i]).intersection(hash_edges[j]))
                
        with nogil, parallel(num_threads=4):
            for i in prange(n,schedule='static'):
                for j in range(i,n):
62
                    if  n_nodes[i] > 0 and n_nodes[j] > 0  and selected_test[i] == True:
Fize Jacques's avatar
Fize Jacques committed
63 64 65 66 67 68 69 70 71
                        denom=n_nodes[i]+n_nodes[j]+\
                              n_edges[i]+n_edges[j]
                        if denom == 0:
                            continue
                        comparison_matrix[i][j]=(2*(intersect_len_nodes[i][j]
                                                  +intersect_len_edges[i][j]))/denom # Data = True --> For nx.MultiDiGraph

                    comparison_matrix[i][j] = comparison_matrix[i][j]
        return np.array(comparison_matrix)
Fize Jacques's avatar
Fize Jacques committed
72 73 74