Search

In this article, our ultimate goal is to transform a graph’s adjacency matrix into a distance matrix. Because cluster density is not observable prior to the actual clustering, our goal is to find a distance whose pairwise minimization will lead to densely connected clusters. Our thesis is centered on the widely accepted notion that strong clusters are sets of vertices with high induced subgraph density. We posit that vertices sharing more connections are closer to each other than vertices sharing fewer connections. This definition of distance differs from the usual shortest-path distance. At the cluster level, our thesis translates into low mean intra-cluster distances, which reflect high densities. We compare three distance measures from the literature. Our benchmark is the accuracy of each measure’s reflection of intra-cluster density, when aggregated (averaged) at the cluster level. We conduct our tests on synthetic graphs, where clusters and intra-cluster density are known in advance. In this article, we restrict our attention to unweighted graphs with no self-loops or multiple edges. We examine the relationship between mean intra-cluster distances and intra-cluster densities. Our numerical experiments show that Jaccard and Otsuka-Ochiai offer very accurate measures of density, when averaged over vertex pairs within clusters.

Graph clustering, also often referred to as network community detection, is the process of assigning common labels to vertices that are densely connected to each other but sparsely connected to the rest of the graph. There are many different approaches to clustering in the literature. However, in this article, we formulate the clustering problem as a combinatorial optimization problem. Our main contribution is a novel problem formulation that maximizes intra-cluster density, a statistically meaningful quantity. It requires the number of clusters, a softbound on cluster size and a penalty coefficient as parameter inputs. More importantly, it is designed to prevent common degeneracies, like the so-called “mega-clusters”. We end with some suggestions on numerical solution techniques and note that an ensemble-like optimization routine seems promising.

A matroid M has all-graphic cocircuits if M ∖ Y is a graphic matroid for every cocircuit Y ∈ C ∗ ( M ) . In Papalamprou and Pitsoulis (2013) it has been shown that signed-graphic matroids that are representable in G F ( 2 ) can be decomposed into graphic matroids and matroids with all-graphic cocircuits. In this paper we study this class of signed-graphic matroids with all-graphic cocircuits and provide the set of regular excluded minors as well as a complete characterization when the matroid is cographic, which in turn results in a simple recognition algorithm.

In this paper, we present a new method for detecting overlapping communities in networks with a predefined number of clusters called LPAM (Link Partitioning Around Medoids). The overlapping communities in the graph are obtained by detecting the disjoint communities in the associated line graph employing link partitioning and partitioning around medoids which are done through the use of a distance function defined on the set of nodes. We consider both the commute distance and amplified commute distance as distance functions. The performance of the LPAM method is evaluated with computational experiments on real life instances, as well as synthetic network benchmarks. For small and medium-size networks, the exact solution was found, while for large networks we found solutions with a heuristic version of the LPAM method.

Recognition algorithms determining whether a given matroid is binary signed-graphic or not are presented in this work. Depending on whether the input is a cographic, a binary or a general matroid different algorithms are provided utilizing mainly decomposition results for the class of signed-graphic matroids. Finally, in order to devise such algorithms, necessary results regarding the representability of signed-graphic matroids in various fields are also given.

Computation of typical statistical sample estimates such as the median or least squares fit usually require the solution of an unconstrained optimization problem with a convex objective function, that can be solved efficiently by various methods. The presence of outliers in the data dictates the computation of a robust estimate, which can be defined as the optimum statistical estimate for a subset that contains at least half of the observations. The resulting problem is now a combinatorial optimization problem which is often computationally intractable. Classical statistical methods for multivariate location $$\varvec{\mu }$$μ and scatter matrix $$\varvec{\varSigma }$$Σ estimation are based on the sample mean vector and covariance matrix, which are very sensitive in the presence of outlier observations. We propose a new method for robust location and scatter estimation which is composed of two stages. In the first stage an unbiased multivariate $$L_{1}$$L1-median center for all the observations is attained by a novel procedure called the least trimmed Euclidean deviations estimator. This robust median defines a coverage set of observations which is used in the second stage to iteratively compute the set of outliers which violate the correlational structure of the data set. Extensive computational experiments indicate that the proposed method outperforms existing methods in accuracy, robustness and computational time.

Complex systems in diverse areas such as biology, sociology and physics are frequently being modelled as graphs, that provide the mathematical framework upon which small scale dynamics between the fundamental elements of the system can reveal large scale system behavior. Community structure in a graph is an important large scale characteristic, and can be described as a natural division of the vertices into densely connected groups, or clusters. Detection of community structure remains up to this date a computationally challenging problem despite the efforts of many researchers from various scientific fields in the past few years. The modularity value of a set of vertex clusters in a graph is a widely used quality measure for community structure, and the relating problem of finding a partition of the vertices into clusters such that the corresponding modularity is maximized is an NP-Hard problem. In this paper we present a Greedy Randomized Adaptive Search Procedure (GRASP) with path relinking, for solving the modularity maximization problem in weighted graphs. A class of {0,1} matrices is introduced that characterizes the family of clusterings in a graph, and a distance function is given that enables us to define an l-neighborhood local search, which generalizes most of the related local search methods that have appeared in the literature. Computational experiments comparing the proposed algorithm with other heuristics from the literature in a set of artificially generated graphs and some well known benchmark instances, indicate that our implementation of GRASP with path relinking consistently produces better quality solutions.

Overlap graphs occur in computational biology and computer science, and have applications in genome sequencing, string compression, and machine scheduling. Given two strings $$s_{i}$$ s i and $$s_{j}$$ s j , their overlap string is defined as the longest string $$v$$ v such that $$s_{i} = uv$$ s i = u v and $$s_{j} = vw$$ s j = v w , for some non empty strings $$u,w$$ u , w , and its length is called the overlap between these two strings. A weighted directed graph is an overlap graph if there exists a set of strings with one-to-one correspondence to the vertices of the graph, such that each arc weight in the graph equals the overlap between the corresponding strings. In this paper, we characterize the class of overlap graphs, and we present a polynomial time recognition algorithm as a direct consequence. Given a weighted directed graph $$G$$ G , the algorithm constructs a set of strings that has $$G$$ G as its overlap graph, or decides that this is not possible.

The shortest superstring problem (SSP) is an $$NP$$ NP -hard combinatorial optimization problem which has attracted the interest of many researchers, due to its applications in computational molecular biology problems such as DNA sequencing, and in computer science problems such as string compression. In this paper a new heuristic algorithm for solving large scale instances of the SSP is presented, which outperforms the natural greedy algorithm in the majority of the tested instances. The proposed method is able to provide multiple near-optimum solutions and admits a natural parallel implementation. Extended computational experiments on a set of SSP instances with known optimum solutions indicate that the new method finds the optimum solution in most of the cases, and its average error relative to the optimum is close to zero.

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.

The presence of groups containing high leverage outliers makes linear regression a difficult problem due to the masking effect. The available high breakdown estimators based on Least Trimmed Squares often do not succeed in detecting masked high leverage outliers in finite samples. An alternative to the LTS estimator, called Penalised Trimmed Squares (PTS) estimator, was introduced by the authors in \cite{ZiouAv:05,ZiAvPi:07} and it appears to be less sensitive to the masking problem. This estimator is defined by a Quadratic Mixed Integer Programming (QMIP) problem, where in the objective function a penalty cost for each observation is included which serves as an upper bound on the residual error for any feasible regression line. Since the PTS does not require presetting the number of outliers to delete from the data set, it has better efficiency with respect to other estimators. However, due to the high computational complexity of the resulting QMIP problem, exact solutions for moderately large regression problems is infeasible. In this paper we further establish the theoretical properties of the PTS estimator, such as high breakdown and efficiency, and propose an approximate algorithm called Fast-PTS to compute the PTS estimator for large data sets efficiently. Extensive computational experiments on sets of benchmark instances with varying degrees of outlier contamination, indicate that the proposed algorithm performs well in identifying groups of high leverage outliers in reasonable computational time., Comment: 27 pages