event thumbnail image
The 13th International Conference on Knowledge Discovery and Data Mining

SCAN: A Structural Clustering Algorithm for Networks

author: Xiaowei Xu, University of Arkansas at Little Rock

Description

Network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. Many algorithms find clusters by maximizing the number of intra-cluster edges. While such algorithms find useful and interesting structures, they tend to fail to identify and isolate two kinds of vertices that play special roles - vertices that bridge clusters (hubs) and vertices that are marginally connected to clusters (outliers). Identifying hubs is useful for applications such as viral marketing and epidemiology since hubs are responsible for spreading ideas or disease. In contrast, outliers have little or no influence, and may be isolated as noise in the data. In this paper, we proposed a novel algorithm called SCAN (Structural Clustering Algorithm for Networks), which detects clusters, hubs and outliers in networks. It clusters vertices based on a structural similarity measure. The algorithm is fast and efficient, visiting each vertex only once. An empirical evaluation of the method using both synthetic and real datasets demonstrates superior performance over other methods such as the modularity-based algorithms.

You might be experiencing some problems with Your Video player.
Slides
0:03 SCAN: A Structural Clustering Algorithm for Networks
0:24 Network Clustering Problem
1:00 An Example of Networks
2:00 A Social Network Model
3:09 The Neighborhood of a Vertex
4:01 Structure Similarity
4:51 Structural Connectivity [1]
7:06 Structure-Connected Clusters
8:59 Algorithm pt 1
9:07 Algorithm pt 2
9:35 Algorithm pt 3
10:05 Algorithm pt 4
10:11 Algorithm pt 5
10:15 Algorithm pt 6
10:17 Algorithm pt 7
10:21 Algorithm pt 8
10:44 Algorithm pt 9

Lecture rating

People found this lecture:
Worth seeing
because it is:
 Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 0:11:06
Flash video Slide Synchronization Windows Media video

!NOW PLAYING
Watch Part 2
Part 2 0:08:33
Flash video Slide Synchronization Windows Media video

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Xiaowei Xu, November 1, 2007 at 1:47 p.m.:

I made a mistake in my presentation slides. The authors of the paper should be "Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, Thomas A. J. Schweiger". I forgot Zhidan Feng in my title slide.

Xiaowei


Write your own review or comment: