China
Africa
Explore chapters and articles related to this topic
A Survey of Partitional and Hierarchical Clustering Algorithms
Published in Charu C. Aggarwal, Chandan K. Reddy, Data Clustering, 2018
Chandan K. Reddy, Bhanukiran Vinzamuri
In a weighted graph, a minimum spanning tree is an acyclic subgraph that covers all the vertices with the minimum edge weights. Prim’s and Kruskal’s algorithms [9] are used for finding the minimum spanning tree (MST) in a weighted graph. In a Euclidean minimum spanning tree (EMST), the data points represent the vertices and the edge weights are computed using the Euclidean distance between two data points. Each edge in an EMST represents the shortest distance between those two points. Using this EMST a divisive clustering method can be developed which removes the largest weighted edge to get two clusterings and subsequently removes the next largest edge to get three clusterings and so on. This process of removing edges from an EMST gives rise to an effective divisive clustering method. The major advantage of this method is that it is able to detect clusters with nonspherical shapes effectively.
Newly enhanced computing algorithm to quantify unavailability of maintained multi-component systems
Published in Stein Haugen, Anne Barros, Coen van Gulijk, Trond Kongsvik, Jan Erik Vinnem, Safety and Reliability – Safe Societies in a Changing World, 2018
In our previous work we developed a new analytical algorithm which is able to carry out exact reliability quantification of highly reliable systems with maintenance (both preventive and corrective). An exponential distribution for the time to a failure is supposed, possibly for the time to restoration. A generalization of the original methodology so as to be used for unavailability quantification of systems with ageing input components with optional lifetime distribution (i.e. where generally distributed failure and repair times were supposed) is developed in (Bris & Byczanski 2017a). A directed acyclic graph was used as a system representation. The algorithm allows take into account highly reliable and maintained input components. The unavailability of a node of an AG is in fact given by going over all possible combinations of probabilities of the input edges (such combinations that cause failure of the node). For example, having 20 input edges, we have regularly a million combinations to be summarized. This process has two disadvantages: first, computing errors can easily be committed, which were discussed and removed in (Bris & Byczanski 2013), and second, it is hard to be computed systems having big nodes with a lot of input edges.
Cyber Terrorism Launched against Smart Cities
Published in Rocky Dr. Termanini, The Nano Age of Digital Immunity Infrastructure Fundamentals and Applications, 2018
To plan an attack on a Smart City, attackers use a well-known graphical method called the directed acyclic graph (DAG, a graph without a cycle). It is made of nodes, which are represented as circles or ovals. Edges are the connections between the nodes. An edge connects two nodes. They are usually represented by lines, or lines with arrows. A directed acyclic graph has a topological ordering which means that the nodes are ordered in sequence—the starting node has a lower value than the ending node. The DAG is a probabilistic causality graph that shows how events are happening according to their respective probabilities of occurrence. Figures 13.1a,b show how cyber terrorists have used causality methods to acquire higher visibility and confidence on the incoming attack.
The geometric convexity on SE(3) and its application to the formation tracking in multi-vehicle systems
Published in International Journal of Control, 2019
Xiuhui Peng, Junyong Sun, Zhiyong Geng
Consider a multi-vehicle systems with N + 1 nodes. The communication in the network can be described by a directed graph , where represents the node set, represents the edge set, A is the adjacent matrix whose element αij = 1 if , otherwise αij = 0. αij = 1 in a directed graph means vehicle i can get information from vehicle j, but not vice versa. A directed tree is a directed graph where every node, except the one called the root which has no parent, has exactly one parent node. In a directed graph, a cycle represents the directed path that starts and ends at the same node. A digraph without cycles is a directed acyclic graph. Any directed tree belongs to the directed acyclic graph. However, the directed graph is different from the directed tree since the directed acyclic graph allows a follower to obtain the information from multiple leaders rather than the directed tree just allows a follower to track one leader. In this paper, the information interaction among the networked vehicles is schematically represented by a directed acyclic graph, in which the node 0 denotes the reference (leader), and others are followers.
Global exponential stabilisation of acyclic traffic networks
Published in International Journal of Control, 2019
Maria Kontorinaki, Iasson Karafyllis, Markos Papageorgiou
(a) From a graph-theoretic point of view, directed acyclic graphs are graphs whose vertices can admit a topological sorting. This means, that their vertices can be ordered in such a way, that the starting endpoint of every edge (joining two vertices) occurs earlier in the ordering than the ending endpoint of the edge. Assigning the vertices of the graph to the components or cells of the network, for any given acyclic network, and by using the previous definition, we are in a position to reorder the cells of the network into a topological sorting. The main consequence of this sorting is that the matrix P = {pi, j: i, j = 1, …, n} ∈ [0, 1]n × n containing the turning rates of the network becomes strictly upper triangular (Godsil & Royle, 2013; Kim, 1979, 1982). (b) The necessity of Assumption (H2) is a consequence of our goal for global stabilisation of the network: for global stability results we need to exclude cases that are not controllable via inflow control. Proposition 3.1 in the following section shows that the existence of cycles is incompatible with the existence of a globally stabilising feedback.
Mapping fractional landscape soils and vegetation components from Hyperion satellite imagery using an unsupervised machine-learning workflow
Published in International Journal of Digital Earth, 2018
Michael J. Friedel, Massimo Buscema, Luiz Eduardo Vicente, Fabio Iwashita, Andréa Koga-Vicente
A minimum spanning tree is used to produce an undirected graph of SBs and their association to landscape features (Buscema et al. 2010). This representation is constructed by building a complex global graph of the complete pattern of variation from the ACM connectivity values. Moreover, this method fully exploits the topological meaningfulness of graph-theoretic representations in that actual paths connecting nodes (variables) represent the logical interdependence in explaining the variability in the data set. The minimum spanning tree is arrived at by finding an acyclic subset T of E that connects all of the vertices in the graph and whose total weight (i.e. the total distance) is minimized. The total weight is given by:andwhere T is the spanning tree, di,j is the distance edge, and MST is the T whose weighted sum of edges attains the minimum value.