Internship at Stanford: Community Detection in Social Networks

Summer 2010

Research internship at Stanford with Prof. Jure Leskovec. Investigated and developed methods for community detection in large social networks based on Clique percolation method.

Many real-world networks display community structure, i.e. their nodes are organized into groups, called communities, clusters or modules. Communities could represent proteins with similar function in protein-protein interaction networks, groups of friends in social networks, or websites on similar topics on the Web graph. Identifying communities may offer insight on how the network is organised and structured.

During my internship, I studied different approaches for computing community structures. I developed methods for computing cliques and quasi-cliques (densely inter-connected nodes) for large graphs, and implemented the Clique percolation method for overlapping community (clique) detection. I applied these methods to several large social networks and analyzed the community structure in these networks.

Code (GitHub) (advanced SNAP components folder)

Other resources: Community detection in graphs (Santo Fortunato, 2009)