On The Isoperimetric Spectrum of Graphs and Its Approximations

In this paper we consider higher isoperimetric numbers of a (finite directed) graph. In this regard we focus on the $n$th mean isoperimetric constant of a directed graph as the minimum of the mean outgoing normalized flows from a given set of $n$ disjoint subsets of the vertex set of the graph. We show that the second mean isoperimetric constant in this general setting, coincides with (the mean version of) the classical Cheeger constant of the graph, while for the rest of the spectrum we show that there is a fundamental difference between the $n$th isoperimetric constant and the number obtained by taking the minimum over all $n$-partitions. In this direction, we show that our definition is the correct one in the sense that it satisfies a Federer-Fleming-type theorem, and we also define and present examples for the concept of a supergeometric graph as a graph whose mean isoperimetric constants are attained on partitions at all levels. Moreover, considering the ${bf NP}$-completeness of the isoperimetric problem on graphs, we address ourselves to the approximation problem where we prove general spectral inequalities that give rise to a general Cheeger-type inequality as well. On the other hand, we also consider some algorithmic aspects of the problem where we show connections to orthogonal representations of graphs and following J.~Malik and J.~Shi ($2000$) we study the close relationships to the well-known $k$-means algorithm and normalized cuts method.

Clustering Using Isoperimetric Number of Trees

In this paper we propose a graph-based data clustering algorithm which is based on exact clustering of a minimum spanning tree in terms of a minimum isoperimetry criteria. We show that our basic clustering algorithm runs in $O(n log n)$ and with post-processing in $O(n^2)$ (worst case) time where $n$ is the size of the data set. We also show that our generalized graph model which also allows the use of potentials at vertices can be used to extract a more detailed pack of information as the {it outlier profile} of the data set. In this direction we show that our approach can be used to define the concept of an outlier-set in a precise way and we propose approximation algorithms for finding such sets. We also provide a comparative performance analysis of our algorithm with other related ones and we show that the new clustering algorithm (without the outlier extraction procedure) behaves quite effectively even on hard benchmarks and handmade examples.

On Complexity of Isoperimetric Problems on Trees

This paper is aimed to investigate some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called {it minimum normalized cuts}/{it isoperimteric numbers} defined through taking minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a {it partition}/{it subpartition}. Following the main result of [A. Daneshgar, {it et. al.}, {it On the isoperimetric spectrum of graphs and its approximations}, JCTB, (2010)], it is known that the isoperimetric number and the minimum normalized cut both can be described as ${0,1}$-optimization programs, where the latter one does {it not} admit a relaxation to the reals. We show that the decision problem for the case of taking $k$-partitions and the maximum (called the max normalized cut problem {rm NCP}$^M$) as well as the other two decision problems for the mean version (referred to as {rm IPP}$^m$ and {rm NCP}$^m$) are $NP$-complete problems. On the other hand, we show that the decision problem for the case of taking $k$-subpartitions and the maximum (called the max isoperimetric problem {rm IPP}$^M$) can be solved in {it linear time} for any weighted tree and any $k geq 2$. Based on this fact, we provide polynomial time $O(k)$-approximation algorithms for all differe