Search

Network dismantling problem aims to find a node subset whose removal from a network results in the fragmentation of the network into subcritical connected components at the minimal overall cost. People have always been more interested in the unweighted case where each node has the same cost, while there are few results for the weighted case when nodes have different costs. It is a much more challenging problem in network science. In this paper, we present a novel strategy for this generalized network dismantling problem by characterizing the relationship between blocks and cut nodes. We firstly construct an auxiliary block-cut tree T from the original network G , where the nodes in the tree T have two types which correspond to either blocks or cut nodes of G , and edges of T only exist between two different type of nodes. Then we transform the problem of partitioning G by removing nodes to the problem of partitioning T by removing edges, both at a minimum overall cost. Finally partitioning T can be solved by a weighted spectral clustering algorithm. When we apply this new strategy on real-world networks, it performs equally or even better than the current state-of-the-art methods. [ABSTRACT FROM AUTHOR]

For an undirected network G = (V , E) with removal cost on each node, the generalized network dismantling problem is to find a node subset S ⊆ V with the minimum overall removal cost, such that the size of each connected component in G − S is not larger than a given integer K. This issue has wide applications at network destruction (e.g., combating crime network) or network defense (e.g., strengthening the infrastructure), and has gained growing attentions from various research fields. In graph theory, cut nodes play important roles in ensuring network connectivity, which could of course be regarded as potential removal candidates for this network dismantling problem. This paper is primarily dedicated to this point. Here, having the aid of an auxiliary block-cut tree, we transform the network dismantling problem into a relatively simple problem − − tree dismantling problem, and then design a bottom-up dynamic programming algorithm (abbreviated as DPA) to dismantle this auxiliary tree by removing cut nodes with minimum overall removal costs. This DPA dismantling strategy has been tested on both synthetic networks and real-world networks, and numerical experiments demonstrate the superiority of this method. Our results shed light on more explorations of network structure from the cut-node perspectives. • Allowed to take arbitrary non-negative real values as removal costs. • An auxiliary tree-structure built to create an efficient dynamic programming algorithm. • Randomization verifies superiority in handling generalized dismantling problems. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to present some ways of constructing a lattice ordered effect algebra from the given family of MV-algebras. The loop lemma of lattice ordered effect algebras is proved. Then the definitions of Greechie diagrams of effect algebras are given. All these results have generalized those of orthomodular lattices. As applications of loop lemma and Greechie diagrams, some lattice ordered effect algebras without states are presented. [Copyright &y& Elsevier]

A tolerance is a reflexive and symmetric, but not necessarily transitive, binary relation. Contrary to what happens with equivalence relations, when dealing with tolerances one must distinguish between blocks (maximal subsets where the tolerance is a total relation) and classes (the class of an element is the set of those elements tolerable with it). Both blocks and classes of a tolerance on a set define coverings of this set, but not every covering of a set is defined in this way. The characterization of those coverings that are families of blocks of some tolerance has been known for more than a decade now. In this paper we give a characterization of those coverings of a finite set that are families of classes of some tolerance. [ABSTRACT FROM AUTHOR]

Data base management systems have grown rapidly in their power and complexity over the 15-year history of data processing on commercially available computers. The original concepts have split, and new terms have been adopted to name and refer to these concepts. The Data Structure Diagram graphic technique is used to illustrate the splitting of the concepts and the structural relations which exist between these concepts at each point in the evolution. [ABSTRACT FROM AUTHOR]