Graph Clustering With Network Structure Indices

author: Matthew J. Rattigan, University of Massachusetts Amherst
published: June 23, 2007,   recorded: June 2007,   views: 8052


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.


Graph clustering has become ubiquitous in the study of relational data sets. We examine two simple algorithms: a new graphical adaptation of the k -medoids algorithm and the Girvan-Newman method based on edge betweenness centrality. We show that they can be effective at discovering the latent groups or communities that are defined by the link structure of a graph. However, both approaches rely on prohibitively expensive computations, given the size of modern relational data sets. Network structure indices (NSIs) are a proven technique for indexing network structure and efficiently finding short paths. We show how incorporating NSIs into these graph clustering algorithms can overcome these complexity limitations. We also present promising quantitative and qualitative evaluations of the modified algorithms on synthetic and real data sets.

See Also:

Download slides icon Download slides: icml07_corvallis_rattigan_matthew.pdf (13.6┬á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 Tammie Rhouk, March 4, 2020 at 2:49 p.m.:

In this video, relationship between pattern analysis, statistical modelling, and computational learning have been explained in a very beautiful manner. This understanding would help students in improving their machine learning skills. Glad to visit website for choosing invitational speech topics that made easy for us to prepare papers on them.

Write your own review or comment:

make sure you have javascript enabled or clear this field: