Location: Conferences » Complex Systems Society » 4th European Phd Complexity School

Community structure in graphs

author:Santo Fortunato, Institute for Scientific Interchange Foundation
published: Oct. 15, 2008,   recorded: September 2008,   views: 154
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 Outline
0:04 “Communities”
1:01 Versions
1:48 Outline
3:18 Questions
3:24 Communities: definition
4:32 What is a partition?
5:24 Overlapping communities
6:09 Hierarchies
6:52 What is a “good” partition?
7:14 How can we compare different partitions?
7:52 Quality function Q
8:20 Modularity
10:35 History
11:59 Graph partitioning
13:11 If cluster sizes are not specified...
13:55 Spectral partitioning
15:03 Spectral properties of L
16:49 If the network is connected...
19:38 Kernighan-Lin algorithm
22:33 Hierarchical clustering
27:11 Final result: a hierarchy of partitions (dendrogram)
28:36 Problems of traditional methods
30:03 Girvan-Newman algorithm
31:24 Link-betweenness: number of shortest paths crossing a link
32:50 Steps
33:30 The process delivers a hierarchy of partitions: which one is the best?
34:48 New methods
36:13 Modularity optimization
37:27 Greedy algorithm
41:25 Resolution limit of modularity
41:28 S.F. & M. Barthélemy
43:26 Dynamic algorithms
44:49 Clique percolation
46:31 Testing algorithm
47:31 Benchmark of Girvan & Newman
50:54 Problems
51:36 New benchmark
52:47 Graphs 1
54:02 Graphs 2
54:35 Real networks
56:10 Open problems
57:56 S. F., C. Castellano
62:31 - Questions

Related content

Visitors who watched this lecture also watched...

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.

Description

Identifying communities in networks is an open challenge of fundamental importance in several disciplines. Here I discuss the main aspects of the problem, from the definition of community to the problem of hierarchy, including the crucial issue of testing methods of community detection.

See Also:

Download article icon Download article: ephdcs08_fortunato_csig_01.pdf (2.0 MB)

Download slides icon Download slides: ephdcs08_fortunato_csig_01.ppt (3.1 MB)

Launch Windows Media PlayerLaunch in a standalone WM Player

WMedia PlayerSwitch to Windows Media Player

View slides View slides

Help icon Streaming Video Help

WebLink icon Windows Media Player Firefox Plugin - Download

Link this page  

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

Write your own review or comment:

make sure you have javascript enabled or clear this field: