kernel Spectral Clustering for Community Detection in Complex Networks

Abstract--This paper proposes a kernel spectral clustering approach for community detection in unweighted networks. The authors employ the primal-dual framework and make use of out-of-sample extension. They also propose a method to extract from a network a subgraph representative for the overall community structure. The commonly used modularity statistic is used as a model selection procedure. The effectiveness of the model is demonstrated through synthetic networks and benchmark real network data.

Problem Setup

Network

A network (graph) consists of a set of vertices or nodes and a collection of edges that connect pairs of nodes. A way to represent a network with [math]\displaystyle{ N }[/math] nodes is to use a similarity matrix [math]\displaystyle{ S }[/math], which is an