|
3:30 pm, Seminar Hall On Graph Density Dr. Sambuddha Roy IBM Research, New Delhi. 25-02-14 Abstract The problem of finding \textit{communities} in \textit{large} networks is an important primitive in data analysis. There are several applications of this: community mining, spam detection, discovery of biological network modules, etc. Naturally there are certain choices of what we mean by a ``community''. Roughly a community may refer to a well-connected subgraph of the entire network. As an instance, the \textit{minimum degree} of a subgraph can be considered as a reasonable measure of how connected the graph is. A more realistic measure of connectivity of a graph is its \textit{average} degree. This leads us to the notion of the \textit{density} of a graph $G$. The density of a graph $G$ is the quantity ${|E(G)|}/{|V(G)|}$. It is clear that the density of a graph $G$ is \textit{half} of its average degree. Given a graph $G$, the \textbf{Densest Subgraph} problem is to find the subgraph $H$ of maximum density. It is well known (Goldberg'84) that the Densest Subgraph problem is solvable in polynomial time. However, such algorithms are typically $\lp$ based; consequently, they are rather inefficient when considered for massive graphs. Our talk will concentrate on two aspects of the Densest Subgraph problem: subject to various general forms of constraints, and deriving near-linear time (approximate) algorithms for finding the densest subgraph. This talk will be largely self-contained; we will survey some of the recent results in the area of graph density and explore various generalizations. This is based on joint work with Venkatesan Chakaravarthy, Natwar Modani, Sivaramakrishnan Natarajan, Yogish Sabharwal.
|
