Search

Betweenness centrality (BC) is a measure of the importance of a vertex in a graph, which is defined using the number of the shortest paths passing through the vertex. Brandes proposed an efficient algorithm for computing the BC scores of all vertices in a graph, which accumulates pair dependencies while traversing single-source shortest paths. Although this algorithm works well on static graphs, its direct application to dynamic graphs takes a huge amount of computation time because the BC scores must be computed from scratch every time the structure of graph changes. Therefore, various algorithms for updating the BC scores of all vertices have been developed so far. In this article, we propose a novel algorithm for updating the BC scores of all vertices in a graph upon deletion of a single edge. We also show the validity and efficiency of the proposed algorithm through theoretical analysis and experiments using various graphs obtained from synthetic and real networks. [ABSTRACT FROM AUTHOR]

Stable patterns that can be realized by a class of 1-D two-layer cellular neural networks (CNNs) are studied in this paper. We first introduce the notions of potentially stable pattern, potentially stable local pattern, and local pattern set. We then show that all of 256 possible sets can be realized as the local pattern set of the two-layer CNN, while only 59 sets can be realized as the local pattern set of the single-layer CNN. We also propose a simple way to optimize the template values of the CNN, which is formulated as a set of linear programming problems, and present the obtained values for all of 256 sets. Index Terms--Cellular neural networks (CNNs), hidden layer, stable patterns, template optimization, two layers.

Global convergence of the sequential minimal optimization (SMO) algorithm for support vector regression (SVR) is studied in this paper. Given I training samples, SVR is formulated as a convex quadratic programming (QP) problem with I pairs of variables. We prove that if two pairs of variables violating the optimality condition are chosen for update in each step and subproblems are solved in a certain way, then the SMO algorithm always stops within a finite number of iterations after finding an optimal solution. Also, efficient implementation techniques for the SMO algorithm are presented and compared experimentally with other SMO algorithms. Index Terms--Convergence, quadratic programming (QP), sequential minimal optimization (SMO), support vector regression (SVR).

Decomposition methods are well-known techniques for solving quadratic programming (QP) problems arising in support vector machines (SVMs). In each iteration of a decomposition method, a small number of variables are selected and a QP problem with only the selected variables is solved. Since large matrix computations are not required, decomposition methods are applicable to large QP problems. In this paper, we will make a rigorous analysis of the global convergence of general decomposition methods for SVMs. We first introduce a relaxed version of the optimality condition for the QP problems and then prove that a decomposition method reaches a solution satisfying this relaxed optimality condition within a finite number of iterations under a very mild condition on how to select variables. Index Terms--Decomposition method, global convergence, quadratic programming (QP), support vector machines (SVMs), termination.

We study global dynamical behavior of cellular neural networks (CNNs) consisting of two cells. Since the output characteristic of each cell is expressed by a piecewise-linear function, a CNN with two cells is considered as a planar piecewise-linear dynamical system. We present the necessary and sufficient condition for such a CNN to be completely stable under the assumptions that: 1) self-coupling coefficients take the same value greater than one and 2) biases are set to zero. The condition is explicitly expressed in terms of coupling coefficients between cells. Index Terms--Cellular neural networks (CNNs), complete stability, planar dynamical systems.

Realization of associative memories by cellular neural networks (CNNs) with binary output is studied. Concerning this problem, a CNN design method based upon generalized eigenvalue minimization (GEVM) has recently been proposed. In this brief, a new CNN design method which is based on the GEVM-based method will be presented. We first give some analytical results related to the basin of attraction of a memory vector. We then derive the design method by combining these analytical results and the GEVM-based method. We finally show through computer simulations that the proposed method can achieve higher recall probability than the original GEVM-based method. Index Terms--Associative memory, basin of attraction, cellular neural networks (CNNs), generalized eigenvalue minimization (GEVM).

This paper gives a new sufficient condition for complete stability of a nonsymmetric cellular neural network (CNN). The convergence theorem of the Gauss - Seidel method, which is an iterative technique for solving a linear algebraic equation, plays an important role in our proof. It is also shown that the existence of a stable equilibrium point does not imply complete stability of a nonsymmetric CNN. Index Terms - Cellular neural networks, complete stability, Gauss- Seidel method.

This letter gives a new sufficient condition for nonsymmetric CNN's to have at least one stable equilibrium point. Existence of a stable equilibrium point is important for nonsymmetric CNN's because it is a necessary condition for complete stability. It is shown that our sufficient condition is a generalization of a previous result concerning the existence of a stable equilibrium point, and that it can easily be applied to space-invariant CNN's with a 3 x 3 neighborhood. Index Terms - Cellular neural networks, complete stability, stable equilibrium points.

Sequential minimal optimization (SMO) algorithm is one of the simplest decomposition methods for learning of support vector machines (SVMs). Keerthi and Gilbert have recently studied the convergence property of SMO algorithm and given a proof that SMO algorithm always stops within a finite number of iterations. In this letter, we point out the incompleteness of their proof and give a more rigorous proof. Index Terms--Support vector machines (SVMs), sequential minimal optimization (SMO) algorithm, convergence, termination.