Community detection Q: Given a network how do we find all communities? A: Find weak ties and identify communities Betweenness centrality [Girvan and Newman, PNAS 02]. Modularity [Newman, PNAS 061 Graph partitioning methods [Karypis and Kumar, SISC08 SFI collaboration network[Newman• Q: Given a network, how do we find all communities? • A: Find weak ties and identify communities – Betweenness centrality [Girvan and Newman, PNAS’02], – Modularity [Newman, PNAS’06] – Graph partitioning methods [Karypis and Kumar, SISC’08] SFI collaboration network [Newman] 7 Community Detection