Search

Broadcasting is disseminating information in a network where a specific message must spread to all network vertices as quickly as possible. Finding the minimum broadcast time of a vertex in an arbitrary network is proven to be NP-complete. However, this problem is solvable for a few families of networks. In this paper, we present an optimal algorithm for finding the broadcast time of any vertex in a fully connected tree ( FCT n ) in O (| V | log log n) time. An FCT n is formed by attaching arbitrary trees to vertices of a complete graph of size n where | V | is the total number of vertices in the graph. [ABSTRACT FROM AUTHOR]

As a relaxation of clique in graph theory, k-plex is a powerful tool for analyzing social networks and identifying cohesive structures in graphs. Recently, more and more researchers have concentrated on the algorithms for the maximum k-plex problem. Among those algorithms, a branch-and-bound algorithm proposed very recently shows a good performance on solving large sparse graphs, but does not work well on social networks. In this paper, we propose two novel vertex selection heuristic strategies for branching. The first one employs historical information of vertex reduction, and the second one is a combination of the first heuristic and the degree-based approach. Intensive experiments on Facebook benchmark show that the algorithm combining our heuristics outperforms the state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to the cyclic Kautz digraphs by introducing the family of the subKautz digraphs sK(d, ℓ), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, ℓ) and CK(d, ℓ). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, ℓ) and CK(d, ℓ) are maximally vertex-connected and super-edge-connected. Whereas K(d, ℓ) are optimal with respect to the diameter, we show that sK(d, ℓ) and CK(d, ℓ) are optimal with respect to the mean distance, whose exact values are given for both families when ℓ = 3. Finally, we provide a lower bound on the girth of CK(d, ℓ) and sK(d, ℓ). [ABSTRACT FROM AUTHOR]

Given a source node and a node set, the node-to-set disjoint paths problem is to find disjoint paths from the source node to all nodes from the node set. In this paper, we propose an improved algorithm for the node-to-set disjoint paths problem on bi-rotator graphs. Our result improves the complexity of previous result from to , where n is the dimension of the input graph. [ABSTRACT FROM AUTHOR]

Graphical avatars have gained popularity in many application domains such as three-dimensional (3D) animation movies and animated simulations for product design. However, the methods to edit avatars' behaviors in the 3D graphical environment remained to be a challenging research topic. Since the hand-crafted methods are time-consuming and inefficient, the automatic actions of the avatars are required. To achieve the autonomous behaviors of the avatars, artificial intelligence should be used in this research area. In this paper, we present a novel approach to construct a system of automatic avatars in the 3D graphical environments based on the machine learning techniques. Specific framework is created for controlling the behaviors of avatars, such as classifying the difference among the environments and using hierarchical structure to describe these actions. Because of the requirement of simulating the interactions between avatars and environments after the classification of the environment, Reinforcement Learning is used to compute the policy to control the avatar intelligently in the 3D environment for the solution of the problem of different situations. Thus, our approach has solved problems such as where the levels of the missions will be defined and how the learning algorithm will be used to control the avatars. In this paper, our method to achieve these goals will be presented. The main contributions of this paper are presenting a hierarchical structure to control avatars automatically, developing a method for avatars to recognize environment and presenting an approach for making the policy of avatars' actions intelligently. [ABSTRACT FROM AUTHOR]

A signed graph is an ordered pair , where is a graph G = ( V, E), called the underlying graph of S and is a function from the edge set E of Su into the set {+, -}, called the signature of S. In this paper, we characterize all those signed graphs whose 2-path signed graphs are isomorphic to their square signed graph along with algorithm to check the same. In other sections we find the characterization of signed graph S such that where D is a derived signed graph of the signed graph S such as: line signed graphs, total signed graphs, common edge signed graphs, splitting signed graphs. Also each characterization is supported by algorithms for the same. [ABSTRACT FROM AUTHOR]

In this paper we propose an event-driven way finding algorithm for pedestrians in a graph-based structure. The motivation of each pedestrian is to leave the facility. The events used to redirect pedestrians include the identification of a jam situation and/or identification of a better route than the present. The modeled strategies are the shortest path (local and global); they are combined with a quickest path approach, which is based on an observation principle, i.e. pedestrians take their decisions based on the observed environment and are routed dynamically in the network using an appropriate cost benefit analysis function. The influences of the different strategies on the evacuation time, the individual times spent in jam, the jam size evolution, and the overall jam size itself are investigated. The response of the system to broken escape routes is also analyzed. A good and plausible dynamic response in the route choice behavior of the pedestrians is achieved. [ABSTRACT FROM AUTHOR]

Similarity measurement is crucial for classification. Based on the manifold assumption, many graph-based algorithms were developed. Almost all methods follow the k-rule or ε-rule to construct a graph, and then focus on the algorithms based on the graph. However, the graph may not represent the local structure well, and it does not fully utilize the label information yet. The local structure can be presented by the local density and the distance between the samples and their neighbors. And the graph constructed by the guidance of label information will be better approximate of the relationship of the input data. In this paper, we propose an adaptive semi-supervised graph constructing method. The similarity is learned when constructing the graph. The advantages of the similarity learned by our method include: (1) The similarity is measured along the manifold by constructing a graph; (2) nearby points and points in the same cluster share high similarity; (3) samples from the same class have higher similarity than samples from different classes. Experimental results show that using the proposed similarity for classification task could get better recognition accuracy. [ABSTRACT FROM AUTHOR]

The appearance model is very effective in tracking multiple persons. The main difficulty in tracking persons is to represent appearance reliably and effectively, especially in the presence of occlusions. In this paper, an effective Attributed Relational Graph (ARG) based tracking algorithm is presented to track multiple persons even under occlusions. The appearance of each person is expressed by an ARG model which not only combines color feature with spatial information but also illustrates the relations among body parts. The similarity of ARG models is computed to build a matching matrix in consecutive frames. Four tracking situations are determined according to the matching matrix. In addition, to track persons under occlusions, probabilistic relaxation labeling in the ARG models of body parts is deduced to label occluded persons optimally. Experimental validation of the proposed tracking method is verified and presented on indoor and outdoor sequences. [ABSTRACT FROM AUTHOR]

Spatial outliers are the spatial objects whose nonspatial attribute values are quite different from those of their spatial neighbors. Identification of spatial outliers is an important task for data mining researchers and geographers. A number of algorithms have been developed to detect spatial anomalies in meteorological images, transportation systems, and contagious disease data. In this paper, we propose a set of graph-based algorithms to identify spatial outliers. Our method first constructs a graph based on k-nearest neighbor relationship in spatial domain, assigns the differences of nonspatial attribute as edge weights, and continuously cuts high-weight edges to identify isolated points or regions that are much dissimilar to their neighboring objects. The proposed algorithms have three major advantages compared with other existing spatial outlier detection methods: accurate in detecting both point and region outliers, capable of avoiding false outliers, and capable of computing the local outlierness of an object within subgraphs. We present time complexity of the algorithms, and show experiments conducted on US housing and Census data to demonstrate the effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

Cluster ensemble has proved to be a good alternative when facing cluster analysis problems. It consists of generating a set of clusterings from the same dataset and combining them into a final clustering. The goal of this combination process is to improve the quality of individual data clusterings. Due to the increasing appearance of new methods, their promising results and the great number of applications, we consider that it is necessary to make a critical analysis of the existing techniques and future projections. This paper presents an overview of clustering ensemble methods that can be very useful for the community of clustering practitioners. The characteristics of several methods are discussed, which may help in the selection of the most appropriate one to solve a problem at hand. We also present a taxonomy of these techniques and illustrate some important applications. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel approach to clustering noisy and complex data sets based on the eXtend Classifier Systems (XCS). The proposed approach, termed XCSc, has three main processes: (a) a learning process to evolve the rule population, (b) a rule compacting process to remove redundant rules after the learning process, and (c) a rule merging process to deal with the overlapping rules that commonly occur between the clusters. In the first process, we have modified the clustering mechanisms of the current available XCS and developed a new accelerate learning method to improve the quality of the evolved rule population. In the second process, an effective rule compacting algorithm is utilized. The rule merging process is based on our newly proposed agglomerative hierarchical rule merging algorithm, which comprises the following steps: (i) all the generated rules are modeled by a graph, with each rule representing a node; (ii) the vertices in the graph are merged to form a number of sub-graphs (i.e. rule clusters) under some pre-defined criteria, which generates the final rule set to represent the clusters; (iii) each data is re-checked and assigned to a cluster that it belongs to, guided by the final rule set. In our experiments, we compared the proposed XCSc with CHAMELEON, a benchmark algorithm well known for its excellent performance, on a number of challenging data sets. The results show that the proposed approach outperforms CHAMELEON in the successful rate, and also demonstrates good stability. [ABSTRACT FROM AUTHOR]

Graphs provide us with a powerful and flexible representation formalism for pattern classification. Many classification algorithms have been proposed in the literature. However, the vast majority of these algorithms rely on vectorial data descriptions and cannot directly be applied to graphs. Recently, a growing interest in graph kernel methods can be observed. Graph kernels aim at bridging the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. In the present paper, we propose an approach transforming graphs into n-dimensional real vectors by means of prototype selection and graph edit distance computation. This approach allows one to build graph kernels in a straightforward way. It is not only applicable to graphs, but also to other kind of symbolic data in conjunction with any kind of dissimilarity measure. Thus it is characterized by a high degree of flexibility. With several experimental results, we prove the robustness and flexibility of our new method and show that our approach outperforms other graph classification methods on several graph data sets of diverse nature. [ABSTRACT FROM AUTHOR]

This paper presents a graph-based ordering scheme of color vectors. A complete graph is defined over a filter window and its structure is analyzed to construct an ordering of color vectors. This graph-based ordering is constructed by finding a Hamiltonian path across the color vectors of a filter window by a two-step algorithm. The first step extracts, by decimating a minimum spanning tree, the extreme values of the color set. These extreme values are considered as the infimum and the supremum of the set of color vectors. The second step builds an ordering by constructing a Hamiltonian path among the vectors of color vectors, starting from the infimum and ending at the supremum. The properties of the proposed graph-based ordering of vectors are detailed. Several experiments are conducted to assess its filtering abilities for morphological and median filtering. [ABSTRACT FROM AUTHOR]

Model net proposed in this paper is a kind of directed graph used to represent and analyze the static structure of a modelbase. After the formal definition of the model net was given, a construction algorithm is introduced. Then, two simplification algorithms are put forward to show how this approach can reduce the computational complexity of model composition for a specific decision problem. In succession, a model composition algorithm is worked out based on the simplification algorithms. As a result, this algorithm is capable of finding out all the candidate composite models for a specific decision problem. Finally, several advantages of the model net are discussed briefly. [ABSTRACT FROM AUTHOR]

Graph eigenspaces have been used to encode many different properties of graphs. In this paper we explore how such methods can be used for solving inexact graph matching (the matching of sets of vertices in one graph to those in another) having the same or different numbers of vertices. In this case we explore eigen-subspace projections and vertex clustering (EPS) methods. The correspondence algorithm enables the EPC method to discover a range of correspondence relationships from one-to-one vertex matching to that of inexact (many-to-many) matching of structurally similar subgraphs based on the similarities of their vertex connectivities defined by their positions in the common subspace. Examples in shape recognition and random graphs are used to illustrate this method. [ABSTRACT FROM AUTHOR]

One of the most common ways of representing classes of equivalent Bayesian networks is the use of essential graphs which are also known in the literature as completed patterns or completed pdags. The name essential graph was proposed by Andersson, Madigan and Perlman who also gave a graphical characterization of essential graphs. In this paper an alternative characterization of essential graphs is presented. The main observation is that every essential graph is the largest chain graph within a special class of chain graphs. More precisely, every equivalence class of Bayesian networks is contained in an equivalence class of chain graphs without flags (= certain induced subgraphs). A special operation of legal merging of (connectivity) components for a chain graph without flags is introduced. This operation leads to an algorithm for finding the essential graph on the basis of any graph in that equivalence class of chain graphs without flags which contains the equivalence class of a Bayesian network. In particular, the algorithm may start with any Bayesian network. [ABSTRACT FROM AUTHOR]

Function-Described Graphs (FDGs) have been introduced by the authors as a representation of an ensemble of Attributed Graphs (AGs) for structural pattern recognition alternative to first-order random graphs. Both optimal and approximate algorithms for error-tolerant graph matching, which use a distance measure between AGs and FDGs, have been reported elsewhere. In this paper, both the supervised and the unsupervised synthesis of FDGs from a set of graphs is addressed. First, two procedures are described to synthesize an FDG from a set of commonly labeled AGs or FDGs, respectively. Then, the unsupervised synthesis of FDGs is studied in the context of clustering a set of AGs and obtaining an FDG model for each cluster. Two algorithms based on incremental and hierarchical clustering, respectively, are proposed, which are parameterized by a graph matching method. Some experimental results both on synthetic data and a real 3D-object recognition application show that the proposed algorithms are effective for clustering a set of AGs and synthesizing the FDGs that describe the classes. Moreover, the synthesized FDGs are shown to be useful for pattern recognition thanks to the distance measure and matching algorithm previously reported. [ABSTRACT FROM AUTHOR]

Arrangement graphs and (n,k)-star graphs were introduced as generalizations of star graphs. They were introduced to provide a wider set of choices for the order of topologically attractive interconnection networks. Unidirectional interconnection networks are more appropriate in many applications. Cheng and Lipman, and Day and Tripathi studied the unidirectional star graphs, and Cheng and Lipman studied orientation of arrangement graphs. In this paper, we show that every (n,k)-star graph can be oriented to a maximally are-connected graph when the regularity of the graph is even. If the regularity is odd, then the resulting directed graph can be augmented to a maximally arc-connected directed graph by adding a directed matching. In either case, the diameter of the resulting directed graph is small. Moreover, there exists a simple and near-optimal routing algorithm. [ABSTRACT FROM AUTHOR]