Location: Conferences » The ACM SIGKDD Conference Series - International Conference on Knowledge Discovery & Data Mining » 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), San Jose 2007 » Research Tracks

SCAN: A Structural Clustering Algorithm for Networks

author: Xiaowei Xu, University of Arkansas at Little Rock
published: Sept. 14, 2007,   recorded: September 2007,   views: 15204
Categories

Slides

Related Open Educational Resources

Related content

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.
Lecture popularity: You need to login to cast your vote.
  Bibliography

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 11:06
!NOW PLAYING
Watch Part 2
Part 2 08:33
!NOW PLAYING

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.

See Also:

Download slides icon Download slides: xiaowei-xu-scan.ppt (1.4 MB)

Help icon Streaming Video Help

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

Comment2 Janusz Leidgens, March 16, 2009 at 3:08 p.m.:

I have a problem implementing the algorithm demonstrated in the video and the paper SCAN: A structural Clustering Algorithm for Networks.

To me it seems there is an error in the pseudo code presented.
The video doesn't help very much either.

Greets Janusz Leidgens

Comment3 Xiaowei Xu, July 22, 2011 at 12:47 p.m.:

Dear Janusz:
Please feel free to contact me if you still need the source code of SCAN.

Best regards,
Xiaowei Xu

Comment4 HaizhuShao, August 31, 2011 at 12:27 p.m.:

Dear Xu:
Would you send me your source code of SCAN, I have read your paper,and have to implement it in one month.But I have no idea how to implement it with visual C++.So I need your source to open my brain.Thank you very much.

Comment5 jun li, November 14, 2011 at 6:51 p.m.:

Dear Xu:

Would you send my your source code of SCAN? I am trying to implement it for biological analysis. My email address is:
jli@noble.org. Thanks a lot!

Jun Li

Comment6 David, March 26, 2012 at 11:08 p.m.:

Dear Xu,
Would you mind to send me the source code of SCAN? I read your paper and I would like to use your algorithm for software-defect-localization.
Thank you very much!

David

Comment7 huda, July 8, 2012 at 3:30 a.m.:

Dear Xu,

Could you please send me the source code. to use it in clustering network detection.
This is my email (ml_sir@hotmail.com)

Huda

Comment8 Tuhin Shukla, August 29, 2012 at 4:11 p.m.:

Respected Sir
Could you please send me the source code. to use it in clustering communities. This is my email( tuhinshukla87@rediffmail.com)

Comment9 macun, September 6, 2012 at 3:45 a.m.:

Dear Xu,
I am a student of SICT, I have sent a email to you. Do you get it? On 24,August,you came Shenyang and gave us a perfect speech. I am very interesting your work and I have a lot of questions to ask you. Could you sent email for me?
macun

Comment10 ankita, April 24, 2013 at 4:36 p.m.:

hi
can you please send me your source code on scan algorithm, im currently working on a project that uses scan algorithmm.

thanx

Comment11 khushboo, May 20, 2013 at 12:45 p.m.:

hey,
can u pleaseeee send me the source code for SCAN at my email address: gkhushboo18@yahoo.com.

I have been desperately looking out for this.
thanks in advance.

Comment12 Ningxin, July 7, 2014 at 6:45 p.m.:

Dear Xu,

Could you mind to send me your source code for SCAN? my email address is ningxin.cui.13@ucl.ac.uk

Thank you so much

Comment13 Danny Lee, July 12, 2014 at 3:05 a.m.:

Dear Xu,

Could you mind to send me your source code for SCAN? my email address is emersonhlee@gmail.com. Excellent concept!

Thank you so much

Comment14 zhonghua, July 13, 2015 at 9:32 a.m.:

Dear Xu,

Could you mind to send me your source code for SCAN? my email address is hudsonberger123@gmail.com. Excellent concept!

I have been desperately looking out for this.
thanks in advance.

Comment15 jalal, January 28, 2020 at 6:16 p.m.:

Dear Xu,

Could you mind to send me your source code for SCAN or SCAN++? my email address is jak-007@hotmail.com. Excellent concept!

thanks you So much.

Comment16 Yassine, June 12, 2020 at 5:05 p.m.:

Dear Xu,

Could you mind to send me your source code for SCAN? my email address is hudsonberger123@gmail.com. Excellent concept!

thanks you So much.

Comment17 Yassine, June 12, 2020 at 5:12 p.m.:

Dear Xu,

Could you mind to send me your source code for SCAN? my email address is yassine_chakri@yahoo.de. Excellent concept!

thanks you So much.

Write your own review or comment:

make sure you have javascript enabled or clear this field: