Complex Networks

Network Motif Discovery

 179

Algorithm 9.3 Nauty Alg

1: Input : G

1

(V

1

,E

1

) ⊲ weighted or unweighted

2: Output : G

2

(V

2

,E

2

) : a canonical graph

3:

4: P ← partition of a single cell V

5: S ← stack containing P

6: while S 6= Ø do

7: u ← pop(S)

8: if u = leaf partition then

9: update(G

2

,u)

10: else

11: refine(u)

12: append children of u to S

13: end if

14: end while

1. Find V

i

∈P that has more than one element.

2. ∀v ∈V

i

, compute s

v

= (d(v,V

1

),..., d(v,V

m

)).

3. Divide V

i

into subsets such that all vertices in a subset have the same value of

s

v

.

The procedure is repeated for all V

i

including the ones formed after the split, until

sets cannot be divided anymore.The children ...