Analysis of Community Structure in Social Networks

General Description: This project is an efficient C implementation of a code for analysis the structure of online social networks.

Code Input: The adjacency list of a social graph G = (V, E).

Code Output: All k-cuts.

Project Goal: Detail analysis of social networks structure.

Implementation period: January - April 2011

Technical Details:
This code is an efficient implementation for finding k-cuts of an input graph. The implemented algorithm can efficiently find all k-cuts in large social graphs. It also finds k-whiskers [1] of a graph by recursively running an efficient version of the max-flaw algorithm. The purpose of this project was to propose a more realistic model for underlying structure of online social networks.


[1] J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, 2008.