Search

This paper investigates fully distributed scaled non-negative edge-consensus problems of networked systems with actuator saturation and unmeasurable internal states. By using the adaptive control method, output-feedback-based low-gain technique, and graph theory, a new adaptive algorithm is designed to obtain scaled edge-consensus conditions, under which the difficulties caused by the constraints on edge states and controllers are overcome. There are three interesting characteristics that any global information of networks is not used in this paper's algorithm and result, including the number of vertexes and edges; the feasible solutions of the scaled edge-consensus conditions exist and can be easily obtained; the convergence rate of the controller is adjustable. Furthermore, the designed algorithm is expanded in the cases without actuator saturation. Finally, three examples are given to verify the theoretical results. [ABSTRACT FROM AUTHOR]

This paper concentrates on the bipartite finite-time consensus (BFTC) problem of nonlinear multi-agent systems (MASs) under intermittent communication via event-triggered impulsive control. First, a finite-time consensus (FTC) protocol with an event-triggered mechanism is developed for the MASs with nonlinear dynamics to save limited resources. Then, an impulsive control scheme is introduced to the designed algorithm to further improve the control performance. Based on the structurally balanced graph theory, both antagonistic and cooperative interactions are discussed in this article. Regarding whether the MASs have encountered intermittent communication, sufficient conditions are provided for achieving consensus of the MASs by using the Lyapunov theory and inductive methods. Moreover, the Zeno behavior is excluded. Finally, numerical simulations are given to validate the effectiveness of the algorithm. The result shows that the designed event-triggered BFTC control protocol with an impulsive strategy has a faster convergence rate than that without an impulsive strategy. [ABSTRACT FROM AUTHOR]

All spanning tree generation of a simple connected graph is a well-approached problem in graph theory. In this paper, an algorithm based on a new technique, namely divide-and-conquer, has been proposed. The performance of the proposed algorithm has also been benchmarked against several existing algorithms, including one algorithm implemented in parallel, in this domain. The basis of comparison is on the number of circuits generated and CPU time taken by each of the algorithms compared, using a set of randomly generated graph instances on a common platform. [ABSTRACT FROM AUTHOR]

A fast dynamics model that captures the deployment dynamics of self-actuated, origami-inspired, folded planar spacecraft structures is desired for design and verification applications. In this paper, a general simulation framework for numerically generating the equations of motion of any structure that complies with a set of pattern assumptions is presented. The framework is built through application of the articulated body forward dynamics algorithm and the tree-augmented approach for closed-chain forward dynamics. These are multi-body dynamics approaches developed in the literature for complex robotic manipulator systems. Unique adaptations are required to address the highly constrained nature of a folding structure. This solution is desirable due to the computational efficiency of the base algorithms and the ability to analyze multiple systems without reformulation of the core dynamics algorithm. Baumgarte stabilization techniques are applied to address constraint violations, but are found to be a continuing challenge for folding structures with several closed-chains. • Graph theory analysis of benchmark origami fold patterns is presented. • Dynamics algorithms are adapted for origami-folded spacecraft structures. • The approach is demonstrated with multiple numerical cases and constraint challenges are discussed. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we empirically profile three algorithms for the Shortest Negative Cost Cycle (SNCC) problem. In this problem, we are given a directed, weighted graph G = 〈 V , E , c 〉 , and the goal is to identify a negative cost cycle with the fewest number of edges. The SNCC problem finds applications in a number of domains ranging from program verification to certifying algorithm design. The first polynomial time algorithm for this problem was proposed in Subramani (2009). Since then, several additional techniques, including a randomized approach, have been proposed for the SNCC problem. Our goal in this paper is to analyze three algorithmic paradigms for this problem from the empirical perspective. Towards this end, we profile these algorithmic approaches over a wide range of inputs. Our results indicated that the randomized algorithm is the algorithm of choice over a number of graph classes. [ABSTRACT FROM AUTHOR]

Abstract The paper is devoted to a Gram classification of an important class of signed graphs with loops playing an important role in many branches of mathematics, physics and computer science including game theory, crystallography, Diophantine geometry, Lie theory, spectral graph theory, a graph coloring technique, algebraic methods in graph theory. They have many deep applications in spectral machine learning methods, electrical networks, to link sign prediction in signed unipartite and bipartite networks, and community partition in social networks. We continue the study of finite connected edge-bipartite graphs Δ (bigraphs, for short), with m ≥ 2 vertices (a class of signed graphs), started in Simson (2013) and developed in Simson (2016) by means of the non-symmetric Gram matrix G ˇ Δ ∈ M m (Z) defining Δ , its symmetric Gram matrix G Δ : = 1 2 [ G ˇ Δ + G ˇ Δ t r ] ∈ M m (1 2 Z) , and the Gram quadratic form q Δ : Z m → Z. In the present paper, given n ≥ 1 , we mainly study connected principal Cox-regular edge-bipartite graphs Δ with loops and n + 1 ≥ 2 vertices, in the sense that the symmetric Gram matrix G Δ ∈ M n + 1 (Z) of Δ is positive semi-definite of rank n ≥ 1. Our aim is to classify such edge-bipartite graphs by means of an inflation algorithm, up to the weak Gram Z -congruence Δ ∼ Z Δ ′ , where Δ ∼ Z Δ ′ means that G Δ ′ = B t r ⋅ G Δ ⋅ B , for some B ∈ M n + 1 (Z) with det B = ± 1. Our main result of the paper asserts that, given a principal Cox-regular connected edge-bipartite graph Δ with n + 1 ≥ 2 vertices, there exists an edge-bipartite Euclidean graph D n + 1 of Tables A and B, and a suitably chosen sequence t • − of the inflation operators, each of one of the forms Δ ′ ↦ t a − Δ ′ or Δ ′ ↦ t a b − Δ ′ , such that the composite operator Δ ↦ t • − Δ reduces Δ to the bigraph D n + 1 such that: (i) Δ ∼ Z D n + 1 and (ii) the bigraphs Δ , and D n + 1 have the same number of loops. The algorithm does not change loops and computes a matrix B ∈ M n + 1 (Z) , with det B = ± 1 , defining the weak Gram Z -congruence Δ ∼ Z D n + 1 , that is, satisfying the equation G D n + 1 = B t r ⋅ G Δ ⋅ B. [ABSTRACT FROM AUTHOR]

Abstract Clustering analysis is to classify elements into categories based on their similarity. Clustering by fast search and find of density peaks (CFSFDP) has been proven to be an effective and novel algorithm, which identifies the centers of clusters with density maxima. However, the performance of CFSFDP is quite sensitive to the estimation of densities, that is exactly the selection of the cutoff distance (d c). In a conventional way, the selection of d c is based on subjective experience. It meets difficulties in finding an appropriate d c , especially for detecting nonspherical clusters, because CFSFDP cannot perform well when there are more than one density peak for one cluster. Besides, another barrier of applying CFSFDP is that manual interaction is always required for making an effective selection of cluster centers. In this paper, a new density-based clustering algorithm, clustering by defining and merging candidates of cluster centers via independence and affinity (CDMC-IA), is proposed. With its strategy, an appropriate value of cutoff distance d c can be well suggested and the robustness of the method itself is enhanced. Moreover, CDMC-IA introduces a new quantity independence to sort and select cluster centers, instead of human based selection from decision graph. Another quantity affinity is also introduced, which well handles multiple density peaks existing in one cluster and is able to assign each data point to the its targeted cluster. The performance of applying conventional clustering methods to benchmark datasets will be compared with the proposed method in this paper. [ABSTRACT FROM AUTHOR]

In 2011, Danicic et al. introduced an elegant generalization of the notion of control dependence for any directed graph. They also proposed an algorithm computing the weak control-closure of a subset of graph vertices and performed a paper-and-pencil proof of its correctness. We have performed its machine-checked proof in the Coq proof assistant. This paper also presents a novel, more efficient algorithm called lDFS to compute weak control-closure taking benefit of intermediate propagation results of previous iterations in order to accelerate the following ones. This optimization makes the design of the algorithm more complex and requires subtle loop invariants for its proof. lDFS has been formalized and mechanically proven in the Why3 verification tool. To investigate the impact of several possible optimizations and compare the performances of different versions of the algorithm, we perform experiments on arbitrary generated graphs with up to hundreds of thousands of vertices. They demonstrate that the proposed algorithm remains practical for real-life programs and significantly outperforms all considered versions of Danicic's initial technique. [ABSTRACT FROM AUTHOR]

In the theory and applications of graphs, it is a basic problem to compute the numbers of independent sets and matchings of given sizes. Since the problem of computing the total number of independent sets and that of matchings of graphs is #P-complete, it is unlikely to give efficient algorithms to find the numbers of independent sets and matchings of given sizes. In this paper, for graphs with order n and treewidth at most p , we present two dynamic algorithms to compute the numbers of independent sets of all sizes with runtime O (2 p  ·  pn 3 ) and the numbers of matchings of all sizes with runtime O (2 2 p  ·  pn 3 ), respectively. By the algorithms presented in this paper, for graphs with small treewidths, the numbers of independent sets and matchings of all possible sizes can be computed efficiently. [ABSTRACT FROM AUTHOR]

Taking its inspiration from the visibility algorithm, which was proposed by Lacasa et al. (2008) to convert a time-series into a complex network, this paper develops and proposes a novel expansion of this algorithm that allows generating a visibility graph from a complex network instead of a time-series that is currently applicable. The purpose of this approach is to apply the idea of visibility from the field of time-series to complex networks in order to interpret the network topology as a landscape. Visibility in complex networks is a multivariate property producing an associated visibility graph that maps the ability of a node “to see” other nodes in the network that lie beyond the range of its neighborhood, in terms of a control-attribute. Within this context, this paper examines the visibility topology produced by connectivity (degree) in comparison with the original (source) network, in order to detect what patterns or forces describe the mechanism under which a network is converted to a visibility graph. The overall analysis shows that visibility is a property that increases the connectivity in networks, it may contribute to pattern recognition (among which the detection of the scale-free topology) and it is worth to be applied to complex networks in order to reveal the potential of signal processing beyond the range of its neighborhood. Generally, this paper promotes interdisciplinary research in complex networks providing new insights to network science. [ABSTRACT FROM AUTHOR]

Community detection in complex networks, is to detect the community structure with the internal structure relatively compact and the external structure relatively sparse, according to the topological relationship among nodes in the network. In this paper, we propose a compactness function which combines the weight of nodes, and use it as the objective function to carry out the node label propagation. Firstly, according to the node degree, we find the sets of core nodes which have great influence on the network. The more the connections between the core nodes and the other nodes are, the larger the amount of the information these kernel nodes receive and transform. Then, according to the similarity of the nodes between the core nodes sets and the nodes degree, we assign weights to the nodes in the network. So the label of the nodes with great influence will be the priority in the label propagation process, which effectively improves the accuracy of the label propagation. The compactness function between nodes and communities in this paper is based on the nodes influence. It combines the connections between nodes and communities with the degree of the node belongs to its neighbor communities based on calculating the node weight. The function effectively uses the information of nodes and connections in the network. The experimental results show that the proposed algorithm can achieve good results in the artificial network and large-scale real networks compared with the 8 contrast algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2 -domination number, γ w 2 ( G ) , the 2 -domination number, γ 2 ( G ) , the { 2 } -domination number, γ { 2 } ( G ) , the double domination number, γ × 2 ( G ) , the total { 2 } -domination number, γ t { 2 } ( G ) , and the total double domination number, γ t × 2 ( G ) , where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γ R ( G ) , and two classical parameters, the domination number, γ ( G ) , and the total domination number, γ t ( G ) , we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs. [ABSTRACT FROM AUTHOR]

Calculating and analyzing the number of spanning trees of graphs (network models) is an important and interesting research project in wide variety of fields, such as mathematics, physics, theoretical computer science, chemistry and so on. The number of spanning trees of graphs (models) displays amounts of information on its structural features and also on some relevant dynamical properties, in particular network security, random walks and percolation. In this paper, firstly, due to lots of graphs (models) are built on the basis of various simple and small elements (components), we provide primarily some helpful network-operation, such as link-operation and merge-operation, to generate more realistic and complicated graphs (models). Secondly, considering reliability of fault-tolerance to random faults and of intrusion-tolerance to selectively remove attacks, synchronization capability and diffusion properties of networks, we present an iterative method (algorithm) for computing the total number of spanning trees. As a pellucid example, we apply our method to tree space and cycle space, notice that it is proved to be indeed a better tool. In order to reflect more widely practical meanings, we study its applications in graph theory, including ladder-graph with zero clustering coefficient, wheel-graph having nonzero clustering coefficient as constituent ingredients of maximal planar graphs. In the rest of this paper, we make a brief summary that the method described by us can be designed a program (algorithm) for obtaining easily the exact number of spanning trees of some models. [ABSTRACT FROM AUTHOR]

A circulant graph C n ( a 1 , … , a k ) is a graph with n vertices { v 0 , … , v n − 1 } such that each vertex v i is adjacent to vertices v ( i + a j ) m o d n , for j = 1 , … , k . In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O ( k 3 log 2 n + n ) algorithm for a subclass of 3-chromatic C n ( a 1 , … , a k ) ’s with k ≥ 2 , which are characterized in the paper. [ABSTRACT FROM AUTHOR]

To efficiently develop and utilize unconventional energy, it is essential to investigate the characteristics of 3D crack network expansion during sandstone hydraulic fracturing (HF). This paper presents the results of physical simulation experiments of sandstone HF under varying shear stress levels, where CT image data acquisition was used to enable 3D reconstruction and establishment of identification algorithms for 3D crack network. The graph theory representation method of crack network was improved using the intersection and extension of crack branch elements as precursors for two vertex sets U and V of a bipartite graph G = (U , V , E) , extending the topological structure representation method to 3D crack network. Using topology and fractal theory, a quantitative characterization method of crack network was developed, which comprehensively considered topological structure parameters and fractal dimension. The findings showed that the fractal dimension of the crack increases linearly with the increase of the shear stress level, and the parameters of the crack topological structure increased first and then decreased. While the parameters of the crack topological structure first increased and then decreased. • Experiments on hydraulic fracturing of sandstone were conducted under varying shear stress levels. • Algorithms were established for the identifying 3D crack network. • The graph theory representation method was developed to analyze the crack network. • The relationship between fracture network expansion and fractal dimension was investigated. [ABSTRACT FROM AUTHOR]

Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more general parameter clique-width, Hamiltonian Cycle becomes W[1]-hard, as shown by Fomin et al. (2010). Sæther and Telle address this problem in their paper (Sæther and Telle, 2016) by introducing a new parameter, split-matching-width, which lies between treewidth and clique-width in terms of generality. They show that even though graphs of restricted split-matching-width might be dense, solving problems such as Hamiltonian Cycle can be done in FPT time. Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT (Bodlaender et al., 2013; Fomin et al., 2014), meaning it can be solved in n O ( 1 ) 2 O ( k ) -time. In this paper, using tools from Fomin et al. (2014), we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any “globally constrained” graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in Sæther and Telle (2016) for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. In fact, using our new approximation algorithm, under the Exponential Time Hypothesis, the Hamiltonian Cycle algorithm of this paper, and the three algorithms for MaxCut, Edge Dominating Set, and Chromatic Number, are asymptotically optimal. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithmic framework for some basic problems on binary images. Algorithms for binary images such as one of extracting a connected component containing a query pixel and that of connected components labeling play basic roles in image processing. Those algorithms usually use linear work space for efficient implementation. In this paper we propose algorithms for several basic problems on binary images which are efficient in time and space, using space-efficient algorithms for grid graphs. More exactly, some of them run in O ( n log n ) time using O ( 1 ) work space and the others run in O ( n ) or O ( n log n ) time using O ( n ) work space for a binary image of n pixels stored in a read-only array. [ABSTRACT FROM AUTHOR]

Highlights • Always considered graph edit distance (GED) is a metric if edit functions are a metric. • We discern between GED computed through edit path and graph bijection. • Triangle inequality of edit functions not necessary if GED defined by graph bijection. • Important: usually recognition ratio is maximized in non-metric edit functions. Abstract In the presentation of the graph edit distance in 1983 and other newer bibliography, authors state that it is necessary to apply the distance restrictions (non-negativity, identity of indiscernible elements, symmetry and triangle inequality) to each of the edit functions (insertion, deletion and substitution of nodes and edges) involved in the process of computing the graph edit distance to make the graph edit distance a true distance. Moreover, graph edit distance algorithms presented in the last three decades have been based on mapping the edit path that transforms a graph into the other one into a bijection of the graphs in which some null nodes have been added. In this paper, we show that the triangle inequality does not need to be imposed in each edit function if the graph edit distance is defined through an edit path; however, it is necessary if it is defined as a graph bijection. This is an important finding since the triangle inequality is the only restriction that relates different edit functions and concerns the process of tuning the edit functions given a specific application. Hence, on one hand, it would encourage research to define new algorithms based on the edit path instead of the graph bijection and, on the other hand, use edit functions without the restriction, for instance, that the sum of the costs of insertion and deletion of a pair of nodes has to be larger or equal than the cost of substituting them, which could increase the recognition ratio of a concrete application. [ABSTRACT FROM AUTHOR]

Abstract We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d -degenerate graphs is not nowhere dense, yet domination remains fixed-parameter tractable. Both nowhere dense classes of graphs and d -degenerate graph classes are biclique-free classes, meaning there is an integer t such that no graph in the class contains K t , t as a subgraph. In this paper we show that various domination problems are fixed-parameter tractable on biclique-free classes of graphs. Our algorithms are simple and rely on results from extremal graph theory that bound the number of edges in a t -biclique free graph. In particular, the problems k -Dominating Set , Connected k -Dominating Set , Independent k -Dominating Set and Minimum Weight k -Dominating Set are shown to be FPT, when parameterized by t + k , on graphs not containing K t , t as a subgraph. With the exception of Connected k -Dominating Set all described algorithms are linear in the size of the input graph. [ABSTRACT FROM AUTHOR]

Highlights • Two incidence matrices are proposed for complete modeling of distribution systems. • A review of various distributed generations is provided in power flow studies. • An efficient power flow algorithm for distribution systems is proposed. • Constant power-voltage buses are handled by a new in-program sensitivity matrix. • Accuracy, performance, and robustness of the model are validated by simulations. Abstract Real-time operation, analysis and control of active distribution systems (DSs) mainly rely on accurate power flow (PF) results. Almost all decisions are made considering PF calculations. On the other hand, efficiency of PF algorithm should be updated to comply with new smart grid paradigms which affect traditional management methods of DSs. A new graph theory based PF algorithm is proposed in this paper for active electrical DSs including various distributed generation (DG) models, three phase equipment and meshed topologies. At first, two incidence matrices are proposed for modeling of DSs. These matrices could successfully handle meshed topologies and unbalanced networks. They could also be modified to consider various three phase equipment such as transformers and voltage regulators. Moreover, a comprehensive study of various modeling methods of DGs in PF studies is presented. In order to handle DG models, a new sensitivity matrix is proposed for in-algorithm calculation of reactive power injection of PV buses. Since, the proposed incidence matrices provide a decoupled model of the network, any topology and characteristic change could be simply applied in this PF algorithm. The proposed PF algorithm was tested in several simulations in various test systems. The results of accuracy test, performance test, and robustness test show capability of the proposed PF algorithm for handling various situations in different PF calculations. [ABSTRACT FROM AUTHOR]

Abstract An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S , where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim e (G). It follows that 1 ≤ dim e (G) ≤ n − 1 for any n -vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O (n 3) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful. [ABSTRACT FROM AUTHOR]

Abstract How to observe the state of a network from a limited number of measurements has become an important issue in complex networks, engineering, communication, epidemiology, etc. Under some scenarios, it is either unfeasible or unnecessary to observe the entire network. Therefore, we investigate the target observation of a network in this paper. We propose a target minimal dominating set problem corresponding to target observation, which is a natural generalization of classical minimal dominating set problem. Three algorithms are proposed to approximate the minimum set of occupied nodes sufficient for target observation. Extensive numerical results on computer-generated random networks and real-world networks demonstrate that the proposed algorithms offer superior performance in identification of a target minimal dominating set. Highlights • We propose a target minimum dominating set problem on networks. • We propose three solving algorithms. • We compare two mechanisms for selection the target nodes. [ABSTRACT FROM AUTHOR]

Highlights • Networks and graphs are naturally embedded in Euclidean hyperspheres. • Communicability embedding of networks/graphs reveals clusters in networks. • Nonmetric multidimensional scaling allows visualization of networks in 3D communicability space. • Communicability clusters of papers in a citation network reveal levels of mathematization. • Communicability clusters in a gene-gene network reveal genes that co-participate in cancer and other diseases. Abstract A complex network is a condensed representation of the relational topological framework of a complex system. A main reason for the existence of such networks is the transmission of items through the entities of these complex systems. Here, we consider a communicability function that accounts for the routes through which items flow on networks. Such a function induces a natural embedding of a network in a Euclidean high-dimensional sphere. We use one of the geometric parameters of this embedding, namely the angle between the position vectors of the nodes in the hyperspheres, to extract structural information from networks. First we propose a simple method for visualizing networks by reducing the dimensionality of the communicability space to 3-dimensional spheres. Secondly, we use clustering analysis to cluster the nodes of the networks based on their similarities in terms of their capacity to successfully deliver information through the network. After testing these approaches in benchmark networks and compare them with the most used clustering methods in networks we analyze two real-world examples. In the first, consisting of a citation network, we discover citation groups that reflect the level of mathematics used in their publications. In the second, we discover groups of genes that coparticipate in human diseases, reporting a few genes that coparticipate in cancer and other diseases. Both examples emphasize the potential of the current methodology for the discovery of new patterns in relational data. [ABSTRACT FROM AUTHOR]

Abstract Community detection in complex networks is a topic of high interest in many fields. In this paper, we propose a new algorithm based on communicability distance for community detection in network(CD algorithm). Furthermore, the accuracy and efficiency of this algorithm are tested by some representative real-world networks and computer-generated networks(GN networks). The experimental results indicate that the CD algorithm can accurately and effectively detect the community structure in these networks with higher values of modularity. Highlights • A new complex network community structure partitioning algorithm is proposed. • A new understanding of the communicability distance through the concept of vertex vector. • Reveal the important role of communicability distance in the detection of community structure from another angle. • This algorithm works well for different networks. [ABSTRACT FROM AUTHOR]

Abstract As many forms of social interactions are transient in nature, that is to say, the social network structure formed by relations between individuals evolves constantly. In practice, exploring influence maximization for product publicity and advertisement marking in dynamic networks is more challenging. Therefore, the research of dynamic influence maximization problem (DIMP) is indispensable. In this paper, we propose an efficient algorithm, T × o n e Hop approach, to solve the DIMP only by updating the nodes affected by the new adding seed node under the dynamic independent cascade model. It means that the seed set and pseudo-seed set always activate their neighbors within one hop in a signal snapshot graph whose total number is T. Consequently, the transfer process is similar to T × o n e hops of propagation in the static network. The experiment evaluations with three real social networks show that our method outperforms forward algorithm and weighted degree algorithm. In addition, our method precedes forward algorithm on running time. Finally, we find out that the common seed nodes number increases with the similarity of two consecutive snapshot graphs. Highlights • We build the derivation of formula and propose an efficient algorithm for the DIMP. • Our method outperforms forward algorithm and weighted degree algorithm. • The actual influence is smaller than the calculation influence when many circles exist. • The common seed number increases with the similarity of two consecutive snapshots. [ABSTRACT FROM AUTHOR]

Abstract Several graph theoretic watermark methods have been proposed to encode numbers as graph structures in software watermarking environments. In this paper we propose an efficient and easily implementable codec system for encoding watermark numbers as reducible permutation flow-graphs and, thus, we extend the class of graphs used in such a watermarking environment. More precisely, we present an algorithm for encoding a watermark number w as a self-inverting permutation π ∗ , an algorithm for encoding the self-inverting permutation π ∗ into a reducible permutation graph F [ π ∗ ] whose structure resembles the structure of real program graphs, as well as decoding algorithms which extract the permutation π ∗ from the reducible permutation graph F [ π ∗ ] and the number w from π ∗. Both the encoding and the decoding process take, in the worst-case, time and space linear in the length of the binary representation of w. The two main components of our proposed codec system, i.e., the self-inverting permutation π ∗ and the reducible permutation graph F [ π ∗ ] , incorporate the binary representation of the watermark w in their structure and possess important structural properties, which make our system resilient to attacks; to this end, we experimentally evaluated our system under edge modification attacks on the graph F [ π ∗ ] and the results suggest that we can detect such attacks with high probability. [ABSTRACT FROM AUTHOR]

Highlights • The approach takes into account the complexity of failure mechanisms as a system and integrates both expert knowledge and diagnostic information. • The diagnostic algorithm enables to detect active failure mechanisms and track their progression based on diagnostic information from different sources. • The prognostic algorithm enables to predict the occurrence of failure modes dynamically as new information becomes available. • The simplicity of the algorithms and graphical representation of the results helps to build decision-makers' trust. • A case study on hydroelectric generator stator is proposed. Abstract The aim of this paper is to propose a holistic multi-failure mode prognosis approach that takes into account the complexity of failure mechanisms as a system. Model assumptions are first proposed by experts and then formalized using graph theory and stochastic models. The prognosis approach relies on a diagnostic algorithm that combines diagnostic information from different sources (e.g., measurements and inspections) to detect active failure mechanisms and track their progression, and a prognostic algorithm that predicts failure mode occurrences dynamically as new information becomes available. Furthermore, the approach identifies undetectable failure mechanisms where no symptoms have yet been measured. The relative simplicity of the algorithms and graphical representation of the results helps to build decision-makers' trust. In addition, the approach is a means of capturing acquired knowledge and available data. A case study of a hydroelectric generator stator is proposed. The resulting multi-state degradation model identified more than 150 failure mechanisms discretized in 70 physical states and leading to three failure modes. Three historical failure and one online case studies are presented, based on diagnostic data from Hydro-Québec's generating fleet. In two of the case studies, the failure mode occurrence could have been predicted more than eight years in advance. [ABSTRACT FROM AUTHOR]

Highlights • Reducing the graph size by eliminating the nodes based on their degree measure. • Extension to graph edit distance based on node contraction. • Applied the proposed algorithm on letter and AIDS dataset. • Can act as a trade-off between time and accuracy considerations. Abstract Graph matching is the task of computing the similarity between two graphs. It is widely used in graph-based structural pattern recognition. Error-tolerant graph matching is a type of graph matching, in which a similarity between two graphs is computed based on some tolerance value whereas in exact graph matching a strict one-to-one correspondence is required between two graphs. In this paper, we present an approach to error-tolerant graph matching using node contraction where the given graph is transformed into another graph by contracting smaller degree nodes. We use this scheme to extend the notion of graph edit distance, which can be used as a trade-off between execution time and accuracy requirements of various graph matching applications. [ABSTRACT FROM AUTHOR]

Highlights • we use background weight map to provide seeds for manifold ranking. • we extend the traditional manifold ranking to second-order formula. • we establish a third-order smoothness framework to optimize the saliency map. Abstract Graph-based approaches for saliency detection have attracted much attention and been exploited widely in recent years. In this paper, we present a new method to promote the performance of existing manifold ranking algorithms. Initially, we use background weight map to provide seeds for manifold ranking; Next, we extend the traditional manifold ranking to second-order formula and add a weight mask to its fitting term. Finally, for further improvement of the performance, we establish a third-order smoothness framework to optimize the saliency map. In the experiments, we compare two versions (manifold ranking with and without optimization) of our model with seven previous methods and test them on several benchmark datasets. Different kinds of strategies are also adopted for evaluation and the results demonstrate that our method achieves the state-of-the-art. [ABSTRACT FROM AUTHOR]

Abstract Airline network, including airports as network nodes and flight routes as directed network edges, has a lot of special features such as departure and arrival times, air ticket budget, flight capacity, transportation cost, etc. Thus, analyzing network behavior and service performance for such a network is much more difficult than that for many other networks. In this paper, taking China domestic airline network as a representative, we try to discuss the reachability issue for each airport respectively, which could reflect its regional connectivity level and service quality of civil aviation. More specifically, we evaluate reachability through many features including node degree, betweenness, closeness, etc. To get the values of some features, we design a fast Dijkstra-based all-pair shortest path algorithm with both time and budget requirements, then use Fenwick Tree to further improve the time efficiency. Actually, it is a shortest path problem with time windows and other constraints. Furthermore, we propose a faster solution by reducing the edges in the duplicated graph as a simplification and then provide the time complexity proof. Finally, we implement Analytic Hierarchy Process (AHP) to convert the reachability feature into numerical values for all airports to measure their service qualities precisely. Our results for China domestic airline network with 210 airports and 69,160 flight routes will definitely become a guide to airline companies and civil aviation administration for their further development and management. [ABSTRACT FROM AUTHOR]

Abstract Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete. [ABSTRACT FROM AUTHOR]

Abstract Given a graph G and a pair of vertices u , v the interval I G [ u , v ] is the set of all vertices that are in some shortest path between u and v. Given a subset X of vertices of G , the interval I G [ X ] of X , is the union of the intervals for all pairs of vertices in X and we say that X is geodetic if its interval do coincide with the set of vertices in the graph. A minimum geodetic set is a minimum cardinality geodetic set of G. The problem of computing a minimum geodetic set is known to be NP-Hard for general graphs but is known to be polynomially solvable for maximal outerplanar graphs. In this paper we show a polynomial time algorithm for finding a minimum geodetic set in general outerplanar graphs. [ABSTRACT FROM AUTHOR]

A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm. [ABSTRACT FROM AUTHOR]

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structures which has a unique linear-sized decomposition tree. We derive an O ( n 2 ) decomposition algorithm and we take advantage of the involution modular decomposition tree to obtain several algorithmic results. It is well-known that cographs (or equivalently P 4 -free graphs) are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, as the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and appears to be exactly the class of (Bull, Gem, Co-Gem, C 5 )-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independent set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has clique-width at most 4 and that a clique-width expression can be computed in linear time. [ABSTRACT FROM AUTHOR]

By resorting to a new matrix product, called semi-tensor product of matrices, this paper investigates the minimum stable set and core of graph, and also presents a number of results and algorithms. By defining a characteristic logical vector and using matrix expressions of logical functions, a new algebraic representation is derived for the externally stable set. Then, based on the algebraic representation, an algorithm is established to find all the externally stable sets. According to this algorithm, a new necessary and sufficient condition is obtained to determine whether a given vertex subset is an absolutely minimum externally stable set or not. Meanwhile, a new algorithm is also obtained to find all the absolutely minimum externally stable sets. Finally, the graph core, which is simultaneously externally stable set and internally stable set, is investigated. Here the internally stable set requires that internal nodes of this set are all disconnected with each other. Using semi-tensor product, some necessary and sufficient conditions are presented, and then an algorithm is established to find all the graph cores. The study of illustrative examples shows that the results/algorithms presented in this paper are effective. [ABSTRACT FROM AUTHOR]

Intelligence analysis is a domain characterized by a torrent of streaming data within which a very small portion contains useful knowledge or actionable intelligence. Intelligence analysts have to sift through the compiled data and weave through a complex web of convoluted connections in an attempt to illuminate information requirements (IR) and maintain situational awareness. Automated methodologies have eased the manual burden of this process to some extent. Data are naturally modeled in a graphical form representing the known people, places, events and the relationships between them. Graph matching algorithms in which an information requirement is formulated as a template graph or situation of interest to be found in the observed data graph have been successfully employed in intelligence analysis processes. Absent from these past contributions is the recognition that partial information requirements, such as indicators and warnings, are not mutually exclusive to a specific IR, and an understanding of the characteristics of the underlying data can lead to significant performance benefits. The knowledge of overlapping template sections forms the motivation for precedence tree guided search and AND/OR templates. Through the recognition of the overlapping sections, a single AND/OR template can be created to answer many information requirements. This paper presents a novel algorithm for the intelligent traversal of an AND/OR template, providing increased algorithmic efficiency over the execution of multiple sequential graph matching instances. This paper focuses on development of an algorithm for intelligent AND/OR template traversal with computational results illustrating the effectiveness of the developed methods. The results indicate a significant improvement in runtime (with a speedup over 5 in some cases) while maintaining a good solution quality (within 2% of multiple AND path graph matching executions) in AND/OR and precedence tree guided graph matching. [ABSTRACT FROM AUTHOR]

We study the problem of finding in a graph an inclusionwise maximal independent set of minimum cardinality, known as minimum maximal independent set or independent dominating set problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with satisfiability , the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271–284] reveals various conditions under which the independent dominating set problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P 2 + P 3 -free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P 3 + P 3 -free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs. [ABSTRACT FROM AUTHOR]

In this paper, using the properties of graph convergence of H(.,.)-accretive operators, we construct a perturbed algorithm for solving systems of ill-posed variational inclusions involving H(.,.)-accretive operators. Under some suitable conditions, we prove that the sequence generated by the proposed method is strongly convergent to the unique solution of the problem. The main results presented in this paper generalize and improve some recent results in the literature. [ABSTRACT FROM AUTHOR]

In a semi-supervised domain adaptation (DA) task, one has access to only few labeled target examples. In this case, the success of DA needs the effective utilization of a large number of unlabeled target data to extract more discriminative information that is useful for generalization. To this end, we exploit in this paper the feature space embeddings of the target data as well as multi-source prior models to augment the discrimination space for the target function learning. Therefore, we propose a novel multi-source adaptation learning framework based on Sparse Feature Space Representation (SFSR), or called SFSR-MSAL for short. Specifically, the SFSR algorithm is first presented for the further construction of robust graph, on which the discriminative information can be smoothly propagated into the unlabeled target data by additionally incorporating the geometric structure of the target data. Considering the robustness in the semi-supervised DA, we replace the traditional l 2 -norm based least squares regression with the l 2, 1 -norm sparse regression, and then construct the SFSR-graph based semi-supervised DA framework with multi-source adaptation constraints. Our framework is universal and can be easily degraded into semi-supervised learning by just tuning the regularization parameter. Moreover, to select the discriminative SFSR-graph Laplacians, we also introduce the ensemble SFSR-graph Laplacians regularization into SFSR-MSAL, thus further improving the performance of SFSR-MSAL. The validity of our methods including semi-supervised and DA learning are examined by several visual recognition tasks on some benchmark datasets, which demonstrate the superiority of our methods in comparison with other related state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) of order n and maximum degree Δ , the NP -complete S - labeling problem consists in finding a labeling of G , i.e. a bijective mapping ϕ : V → { 1 , 2 … n } , such that SL ϕ ( G ) = ∑ u v ∈ E min { ϕ ( u ) , ϕ ( v ) } is minimized. In this paper, we study the S - labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SL ϕ ( G ) , together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs—in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SL ϕ ( G ) ≤ | E | + k is solvable in O ∗ ( 2 2 k ( 2 k ) ! ) time, thus fixed-parameterized tractable in k . We finally show that the S - Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars. [ABSTRACT FROM AUTHOR]

This paper aims to study the stochastic stabilization problem of complex networks without strong connectedness (CNSC). To deal with large-scale complex networks which are not strongly connected, a hierarchical method and a hierarchical algorithm are given, respectively. Meanwhile, we construct a logarithmic Lyapunov function for CNSC. Next, based on the theory of asymptotically autonomous systems, the Lyapunov method and the graph theory, the whole complex network can be stabilized by stabilizing a part of nodes. Then, stability criteria of CNSC are given, whose conditions reflect the relationship between dynamic properties and topology structure clearly. Furthermore, the theoretical results are applied to coupled oscillators on CNSC to ensure the stability. Finally, a numerical example is provided to illustrate the effectiveness and practicability of the results. [ABSTRACT FROM AUTHOR]

The problem of community detection as one of the most important applications of network science can be addressed effectively by multi-objective optimization. In this paper, we aim to present a novel efficient method based on this approach. Also, in this study the idea of using all Pareto fronts to detect overlapping communities is introduced. The proposed method has two main advantages compared to other multi-objective optimization based approaches. The first advantage is scalability, and the second is the ability to find overlapping communities. Despite most of the works, the proposed method is able to find overlapping communities effectively. The new algorithm works by extracting appropriate communities from all the Pareto optimal solutions, instead of choosing the one optimal solution. Empirical experiments on different features of separated and overlapping communities, on both synthetic and real networks show that the proposed method performs better in comparison with other methods. [ABSTRACT FROM AUTHOR]

Abstract Many real-world networks are exposed in complicated environments and may be destroyed easily by various kinds of attacks and errors. With no doubt it is of great significance to promote the anti-attack ability of systems. Besides, analyzing attack models is also of significance. The existing studies about network robustness conducted on weighted or unweighted networks have drawn the conclusion that scale-free networks are fragile under malicious attacks, where the precondition is that the cost of removing a node is equal. In fact, the cost of attacking different nodes is far from equal, thus, the removal cost should be taken into consideration when conducting attacks. In this paper, a malicious attack model considering the cost of attacking nodes, termed as Nodal Attack with Cost (NA C), is first proposed to depict the tolerance of networks. Furthermore, the limitation of resources drives us to design an optimization algorithm based on memetic algorithm (MA), termed as MA- NA C , to search for the optimal combination of nodes with the minimum cost which can destroy networks to the desired degree. The experimental results show that networks perform robust under the high degree adaptive (HDA) attack when there is a great difference between hub nodes and leaf nodes in the attack cost, yet the results are similar to previous studies on the condition that the attack cost gap is minor. In addition, MA- NA C is efficient in finding a relatively small attack cost. Based on the study of cost-optimized network structure and features of attacked nodes obtained by MA- NA C , we find that MA- NA C selects the target nodes by taking into account their effect on network structure, which contributes to the good optimization ability of MA- NA C. Highlights • Practical attacks make networks fragmented rather than make each node isolated. • An attack model considering the cost of attacking nodes is designed accordingly. • A memetic algorithm MA- NA C is proposed to find the relatively low attack cost. • The good performance of MA- NA C is validated on various networks. [ABSTRACT FROM AUTHOR]

Abstract Community detection has attracted plenty of attention in the field of complex networks recently, since communities often play important roles in networked systems. Overlapping communities are one of the characteristics of social networks, describing the phenomenon that a node may belong to more than one social group. Thus, it is necessary to find overlapping community structures for realistic social network analyses. In this paper, we propose a link clustering based memetic algorithm for detecting overlapping communities. Since links usually represent the unique relationships among nodes, link clustering can find link groups with the same characteristics. As a result, nodes are naturally partitioned into multiple communities. The proposed algorithm optimizes a modularity density function which is able to identify densely connected groups of links on the weighted line graph modeling the network, and then maps link communities to node communities based on a novel genotype representation. In our method, the number of communities can be automatically determined. Experimental results on general and sparse networks show that our method can successfully detect overlapping community structures and almost all the overlapping nodes. Highlights • Propose a link clustering based memetic algorithm to detect overlapping communities. • Meme-Link can successfully detect overlapping communities and nodes on both general and sparse networks. • Meme-Link outperforms or performs similarly to the state-of-the-art algorithms in the experiments. [ABSTRACT FROM AUTHOR]

Maximum Edge Biclique and related problems have wide applications in management science, bioinformatics, etc. In this paper, we study parameterized algorithms for Parameterized Edge Biclique problem, Parameterized Edge Biclique Packing problem, Parameterized Biclique Edge Deletion problem, and Parameterized Bipartite Biclique Clustering problem. For the Parameterized Edge Biclique problem, the current best result is of running time O ⁎ ( 2 k ) , and we give a parameterized algorithm of running time O ( n k 2.5 k ⌈ k ⌉ ) , where k is the parameter and n is the number of vertices in the given graph. For the Parameterized Edge Biclique Packing problem, based on randomized divide-and-conquer technique, a parameterized algorithm of running time O ⁎ ( k ⌈ k ⌉ l o g k 4 ( 2 k − 1 ) t ) ) is given, where k is the parameter and t is the number of bicliques in the solution. We study the Parameterized Biclique Edge Deletion problem on bipartite graphs and general graphs, and give parameterized algorithms of running time O ⁎ ( 2 k ) and O ⁎ ( 3 k ) , respectively. For the Parameterized Bipartite Biclique Clustering problem, based on modular decomposition method, a kernel of size O ( k 2 ) and a parameterized algorithm of running time O ( 2.42 k ( n + m ) ) are presented, where k is the parameter, n is the number of vertices, and m is the number of edges in the given graph. [ABSTRACT FROM AUTHOR]

In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing , counting matching , and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3- d matching , we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS. [ABSTRACT FROM AUTHOR]