Power Iteration Graph Clustering With functools Higher Order Methods

Graph mining operations take place on an unprecedented scale, dictating the need for scalability in both algorithms and implementation. In the context of graph partitioning, which tantamounts to community structure discovery, power iteration clustering (PIC) is an important and efficient method since it computes the primary eigenvector of a graph or of the Laplacian thereof. PIC converges for broad categories of matrices and can be applied to non-normal ones. Functional paradigm aspects like list transformations as well as capabilities like partially implemented objects and cached results are offered by the Python module functools. These can be combined with other recent major Python concepts such as decorators and lambda expressions to yield elegant and efficient code. PIC being a matrix free method can benefit from functools. As a concrete application a functional implementation of PIC has been applied to two Twitter graphs with different characteristics with encouraging results as evaluated by the Shilouette score and the Gini index.