kernel Spectral Clustering for Community Detection in Complex Networks: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
'''''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. | '''''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. | ||
= | == Backgrounds == | ||
==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>N</math> nodes is | === 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 ''N'' nodes is to use a similarity matrix ''S'', which is an <math>N\times N</math> matrix. This paper only deals with unweighted networks, where the components of ''S'' is 1 or 0. The matrix ''S'' is called adjacency matrix and <math>S_{ij}=1</math> if there is an edge connecting nodes ''i'' and ''j''; otherwise, <math>S_{ij}=0</math>. The degree matrix ''D'' is defined as a diagonal matrix with diagonal entries <math>d_i=\sum\limits_{j}S_{ij}</math> indicating the degree of node ''i'', i.e. the number of edges connected to node ''i''. | |||
===Community Detection=== | |||
The structure of networks sometimes reveals a high degree of organization. Nodes with similar properties/behaviors are more likely to be linked together and tend to form modules. Discovering such modules is called community detection, which is a hot topic in network data analysis. | |||
== Introduction == | |||
Revision as of 01:52, 16 July 2013
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.
Backgrounds
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 N nodes is to use a similarity matrix S, which is an [math]\displaystyle{ N\times N }[/math] matrix. This paper only deals with unweighted networks, where the components of S is 1 or 0. The matrix S is called adjacency matrix and [math]\displaystyle{ S_{ij}=1 }[/math] if there is an edge connecting nodes i and j; otherwise, [math]\displaystyle{ S_{ij}=0 }[/math]. The degree matrix D is defined as a diagonal matrix with diagonal entries [math]\displaystyle{ d_i=\sum\limits_{j}S_{ij} }[/math] indicating the degree of node i, i.e. the number of edges connected to node i.
Community Detection
The structure of networks sometimes reveals a high degree of organization. Nodes with similar properties/behaviors are more likely to be linked together and tend to form modules. Discovering such modules is called community detection, which is a hot topic in network data analysis.