Spectral Partitioning

This demonstrates spectral partitioning. For this. the lower eigenvectors of the Laplacian are used, since verices "near" each other tend to have similar entries in these. The graph is then recursively bisected, using the next bigger eigenvector, until the desired number of partitions is reached.



In [1]:

    
import networkit

First, we partition some random graph. We try to partition into 10 partitions, and we aim to have them as well balanced as possible. This means that he bisection will use the median of the eigenvector's entries to bisect. In the literature, the approach of using the mean instead can be found. This can be accomplished by setting the balanced parameter to False.



In [2]:

    
G = networkit.generators.ErdosRenyiGenerator(1000, 0.003).generate()
partitioner = networkit.partitioning.SpectralPartitioner(G, 10, balanced=True)
partitioner.run()
zeta = partitioner.getPartition()



In [3]:

    
networkit.partitioning.inspectPartitions(zeta, G)









    



-------------------  ----------
# partitions          10
min partition size    82
max partition size   127
avg. partition size  100
imbalance              1.27
edge cut             993
edge cut (portion)     0.666891
modularity             0.225252
-------------------  ----------

Unfortunately, random graphs do not behave incredibly well. As you can see, the edge cut is rather high. Note: The imbalance will probably not be 1 (as it should be in a balanced case). This is because a clean bisection is not always possible, especially for rather small graphs and cases where the desired number of partitions is not a power of two.

Let's try some mesh-like graphs instead (this takes a while):



In [5]:

    
G = networkit.graphio.readGraph("../../input/airfoil1.graph")
partitioner = networkit.partitioning.SpectralPartitioner(G, 8)
partitioner.run()
zeta = partitioner.getPartition()
networkit.partitioning.inspectPartitions(zeta, G)









    



-------------------  -----------
# partitions           8
min partition size   531
max partition size   532
avg. partition size  531.625
imbalance              1.00071
edge cut             505
edge cut (portion)     0.0410937
modularity             0.833899
-------------------  -----------

Nice results! But wait.. we have an algorithm for spectral drawing lying around, right? (See other notebook...) I wonder what happens if I combine both...



In [6]:

    
colors = { v:  (zeta[v] / zeta.numberOfSubsets()) for v in G.nodes() }
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, layout=layout, figsize=(15,15), coloring = colors, nodeSizes = [35.0]*G.numberOfNodes())

Nice! Let's try another...



In [7]:

    
G = networkit.graphio.readGraph("../../input/wing.graph")
partitioner = networkit.partitioning.SpectralPartitioner(G, 4)
partitioner.run()
zeta = partitioner.getPartition()
networkit.partitioning.inspectPartitions(zeta, G)









    



-------------------  -------------
# partitions             4
min partition size   15508
max partition size   15508
avg. partition size  15508
imbalance                1
edge cut              2425
edge cut (portion)       0.0199516
modularity               0.730045
-------------------  -------------



In [9]:

    
colors = { v:  (zeta[v] / zeta.numberOfSubsets()) for v in G.nodes() }
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, layout=layout, figsize=(15,15), coloring = colors, nodeSizes = [35.0]*G.numberOfNodes())









    



---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-9-c835c589980b> in <module>()
      1 colors = { v:  (zeta[v] / zeta.numberOfSubsets()) for v in G.nodes() }
      2 layout = networkit.viztools.layout.SpectralLayout()
----> 3 networkit.viztasks.drawGraph(G, layout=layout, figsize=(15,15), coloring = colors, nodeSizes = [35.0]*G.numberOfNodes())

/usr/local/lib/python3.4/dist-packages/networkit/viztasks.py in drawGraph(G, figsize, labelled, nodeSizes, layout, coloring)
     27                 pos = None
     28         else:
---> 29                 pos = layout.layout(G)
     30 
     31         if not coloring is None:

/usr/local/lib/python3.4/dist-packages/networkit/viztools/layout.py in layout(self, G)
     79 		"""
     80                 self.graph = G
---> 81                 self._prepareSpectrum()
     82                 self._prepareNormalization()
     83                 self._computePositions()

/usr/local/lib/python3.4/dist-packages/networkit/viztools/layout.py in _prepareSpectrum(self)
     25 
     26         def _prepareSpectrum(self):
---> 27                 spectrum = laplacianEigenvectors(self.graph, cutoff = 2, reverse=True)
     28                 self.eigenvectors = spectrum[1]
     29                 self.eigenvalues = spectrum[0]

/usr/local/lib/python3.4/dist-packages/networkit/algebraic.py in laplacianEigenvectors(G, cutoff, reverse)
    120 
    121 def laplacianEigenvectors(G, cutoff=-1, reverse=False):
--> 122         return symmetricEigenvectors(laplacianMatrix(G), cutoff=cutoff, reverse=reverse)
    123 
    124 def adjacencyEigenvectors(G, cutoff=-1, reverse=False):

/usr/local/lib/python3.4/dist-packages/networkit/algebraic.py in symmetricEigenvectors(matrix, cutoff, reverse)
    109                 mode = "LA"
    110 
--> 111         w, v = scipy.sparse.linalg.eigsh(matrix, cutoff + 1, which=mode)
    112 
    113         orderlist = zip(w, range(0, len(w)))

/usr/lib/python3/dist-packages/scipy/sparse/linalg/eigen/arpack/arpack.py in eigsh(A, k, M, sigma, which, v0, ncv, maxiter, tol, return_eigenvectors, Minv, OPinv, mode)
   1566 
   1567     while not params.converged:
-> 1568         params.iterate()
   1569 
   1570     return params.extract(return_eigenvectors)

/usr/lib/python3/dist-packages/scipy/sparse/linalg/eigen/arpack/arpack.py in iterate(self)
    538             # compute y = Op*x
    539             if self.mode == 1:
--> 540                 self.workd[yslice] = self.OP(self.workd[xslice])
    541             elif self.mode == 2:
    542                 self.workd[xslice] = self.OPb(self.workd[xslice])

/usr/lib/python3/dist-packages/scipy/sparse/base.py in dot(self, other)
    238 
    239         """
--> 240         return self * other
    241 
    242     def __eq__(self, other):

/usr/lib/python3/dist-packages/scipy/sparse/base.py in __mul__(self, other)
    288             # Fast path for the most common case
    289             if other.shape == (N,):
--> 290                 return self._mul_vector(other)
    291             elif other.shape == (N, 1):
    292                 return self._mul_vector(other.ravel()).reshape(M, 1)

/usr/lib/python3/dist-packages/scipy/sparse/coo.py in _mul_vector(self, other)
    378         result = np.zeros(self.shape[0], dtype=upcast_char(self.dtype.char,
    379                                                             other.dtype.char))
--> 380         coo_matvec(self.nnz, self.row, self.col, self.data, other, result)
    381         return result
    382 

/usr/lib/python3/dist-packages/scipy/sparse/sparsetools/coo.py in coo_matvec(*args)
    209         npy_clongdouble_wrapper const [] Xx, npy_clongdouble_wrapper [] Yx)
    210     """
--> 211   return _coo.coo_matvec(*args)
    212 
    213 def coo_count_diagonals(*args):

KeyboardInterrupt:

Here we can observe one very nice fact: Because the two smallest eigenvectors of the Laplacian are used for partitioning as well as for drawing, the two first cuts (forming the first 4 partitions) will always be more or less vertical and horizontal.

And another one, for fun!



In [8]:

    
G = networkit.graphio.readGraph("../../input/4elt.graph")
partitioner = networkit.partitioning.SpectralPartitioner(G, 16)
partitioner.run()
zeta = partitioner.getPartition()
networkit.partitioning.inspectPartitions(zeta, G)









    



-------------------  ------------
# partitions           16
min partition size    975
max partition size    976
avg. partition size   975.375
imbalance               1.00064
edge cut             1584
edge cut (portion)      0.0345264
modularity              0.902973
-------------------  ------------



In [9]:

    
colors = { v:  (zeta[v] / zeta.numberOfSubsets()) for v in G.nodes() }
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, layout=layout, figsize=(15,15), coloring = colors, nodeSizes = [35.0]*G.numberOfNodes())

And a last one... the best known cut for this one (while still being balanced and 16 partitions) is 1000, by the way. See the Internet Graph Archive.



In [ ]:

    
G = networkit.graphio.readGraph("../../input/fe_4elt2.graph")
partitioner = networkit.partitioning.SpectralPartitioner(G, 16)
partitioner.run()
zeta = partitioner.getPartition()
networkit.partitioning.inspectPartitions(zeta, G)









    



-------------------  ------------
# partitions           16
min partition size    696
max partition size    697
avg. partition size   696.438
imbalance               1.00081
edge cut             1547
edge cut (portion)      0.0471388
modularity              0.890359
-------------------  ------------



In [ ]:

    
colors = { v:  (zeta[v] / zeta.numberOfSubsets()) for v in G.nodes() }
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, layout=layout, figsize=(15,15), coloring = colors, nodeSizes = [35.0]*G.numberOfNodes())



In [ ]:

    
G = NetworKit.graph.Graph(10000)
vertices = {}
        
for i in range(0, 100):
    for j in range(0,100):
        # Top
        if j > 0:
            G.addEdge((i * 100 + j), (i * 100 + j - 1))
        # left
        if i > 0:
            G.addEdge((i * 100 + j), ((i - 1) * 100 + j))
            
partitioner = networkit.partitioning.SpectralPartitioner(G, 16)
partitioner.run()
zeta = partitioner.getPartition()
networkit.partitioning.inspectPartitions(zeta, G)



In [ ]:

    
colors = { v:  (zeta[v] / zeta.numberOfSubsets()) for v in G.nodes() }
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, layout=layout, figsize=(15,15), coloring = colors, nodeSizes = [35.0]*G.numberOfNodes())



In [ ]: