3:30 pm, Seminar Hall On Graph Density Dr. Sambuddha Roy IBM Research, New Delhi. 250214 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 wellconnected 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 nearlinear time (approximate) algorithms for finding the densest subgraph. This talk will be largely selfcontained; 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.
