Search

Relations between discrete quantities such as people, genes, or streets can be described by networks, which consist of nodes that are connected by edges. Network analysis aims to identify important nodes in a network and to uncover structural properties of a network. A network is said to be bipartite if its nodes can be subdivided into two nonempty sets such that there are no edges between nodes in the same set. It is a difficult task to determine the closest bipartite network to a given network. This paper describes how a given network can be approximated by a bipartite one by solving a sequence of fairly simple optimization problems. The algorithm also produces a node permutation which makes the possible bipartite nature of the initial adjacency matrix evident, and identifies the two sets of nodes. We finally show how the same procedure can be used to detect the presence of a large anti-community in a network and to identify it., Comment: 30 pages

Circulant preconditioners are commonly used to accelerate the rate of convergence of iterative methods when solving linear systems of equations with a Toeplitz matrix. Block extensions that can be applied when the system has a block Toeplitz matrix with Toeplitz blocks also have been developed. This paper is concerned with preconditioning of linear systems of equations with a symmetric block Toeplitz matrix with symmetric Toeplitz blocks that stem from the discretization of a linear ill-posed problem. The right-hand side of the linear systems represents available data and is assumed to be contaminated by error. These kinds of linear systems arise, e.g., in image deblurring problems. It is important that the preconditioner does not affect the invariant subspace associated with the smallest eigenvalues of the block Toeplitz matrix to avoid severe propagation of the error in the right-hand side. A perturbation result indicates how the dimension of the subspace associated with the smallest eigenvalues should be chosen and allows the determination of a suitable preconditioner when an estimate of the error in the right-hand side is available. This estimate also is used to decide how many iterations to carry out by a minimum residual iterative method. Applications to image restoration are presented., Comment: 13 pages, 8 figures