Finding Community Structure with Performance Guarantees in Complex Networks

Details Finding Community Structure with Performance Guarantees in Complex Networks Finding Community Structure with Performance Guarantees in Complex Networks

2011-08-19

arxiv.org/abs/1108.4034v1

Computer Science

Social and Information Networks

Scientific paper

Many networks including social networks, computer networks, and biological networks are found to divide naturally into communities of densely connected individuals. Finding community structure is one of fundamental problems in network science. Since Newman's suggestion of using \emph{modularity} as a measure to qualify the goodness of community structures, many efficient methods to maximize modularity have been proposed but without a guarantee of optimality. In this paper, we propose two polynomial-time algorithms to the modularity maximization problem with theoretical performance guarantees. The first algorithm comes with a \emph{priori guarantee} that the modularity of found community structure is within a constant factor of the optimal modularity when the network has the power-law degree distribution. Despite being mainly of theoretical interest, to our best knowledge, this is the first approximation algorithm for finding community structure in networks. In our second algorithm, we propose a \emph{sparse metric}, a substantially faster linear programming method for maximizing modularity and apply a rounding technique based on this sparse metric with a \emph{posteriori approximation guarantee}. Our experiments show that the rounding algorithm returns the optimal solutions in most cases and are very scalable, that is, it can run on a network of a few thousand nodes whereas the LP solution in the literature only ran on a network of at most 235 nodes.

Affiliated with

Also associated with

No associations

Rating

Finding Community Structure with Performance Guarantees in Complex Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Community Structure with Performance Guarantees in Complex Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Community Structure with Performance Guarantees in Complex Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-108928