Search

In this paper, we propose and explain the use of anytime algorithms in graph matching (GM). GM methods have been involved in many pattern recognition problems. In such a context, GM methods are part of a more complex retrieval system that imposes time and memory constraints on such methods. Anytime algorithms are well suited for use in such an uncertain environment. An anytime algorithm quickly provides the first solution to the problem, finds a list of improved solutions and eventually converges to the optimal solution instead of providing one and only one solution (i.e., the optimal solution). We describe how to convert a recent depth-first GM method into an anytime one. By constraining the solver, the algorithm creates an anytime heuristic search algorithm that allows a flexible trade-off between the search time and the solution quality. We analyze the properties of the resulting anytime algorithm and consider its performance in terms of the deviation of the provided solution from the optimal or the best one found by a state-of-the-art method. Experiments were carried out on seven different types of graph datasets. Moreover, the adopted algorithm was compared to four approximate error-tolerant GM methods. Results showed that the anytime GM can outperform suboptimal methods by only waiting for a small amount of supplementary time. This conclusion brings into question the usual evidence that claims that it is impossible to use optimal GM methods in real-world applications. [ABSTRACT FROM AUTHOR]

Recently hashing with multiple tables has become attractive in many real life applications, owing to its theoretical guarantee and practical success. To pursue the desired performance, usually great efforts are required on the hashing algorithm design for the specified scenario. Hash bit selection serves as a general method that can provide satisfying performance for different scenarios by utilizing existing hashing algorithms. In this paper, a novel bit selection framework via walks on graph is proposed to support both compact hash code generation and complementary hash table construction. It formulates the selection problem as the subgraphs discovery on an edge- and vertex-weighted graph, where the most desired subset corresponds to the frequently visited ones (bits/tables) in a Markov process. The framework is unified and compatible with different hashing algorithms. For compact code generation, it selects the most independent and informative hash bits using the Markov process over the candidate bit graph. For complementary hash table construction, it exploits the hierarchical authority relations among all candidate bits and separates them into a number of bit subsets as the candidate tables, from which multiple complementary hash tables can be efficiently selected. Experiments are conducted for two important selection scenarios, i.e., hashing using different hashing algorithms and hashing with multiple features. The results indicate that our proposed selection framework achieves significant performance gains over the naive selection methods under different scenarios. [ABSTRACT FROM AUTHOR]

In this paper, we present a simple and fast computational method, the phase space coarse graining algorithm that converts a time series into a directed and weighted complex network. The constructed directed and weighted complex network inherits several properties of the series in its structure. Thereby, periodic series convert into regular networks, and random series do so into random networks. Moreover, chaotic series convert into scale-free networks. It is shown that the phase space coarse graining algorithm allows us to distinguish, identify and describe in detail various time series. Finally, we apply the phase space coarse graining algorithm to the practical observations series, international gasoline regular spot price series and identify its dynamic characteristics. [ABSTRACT FROM AUTHOR]

Evaluating link prediction methods is a hard task in very large complex networks due to the prohibitive computational cost. However, if we consider the lower bound of node pairs’ similarity scores, this task can be greatly optimized. In this paper, we study CN index in the bounded link prediction framework, which is applicable to enormous heterogeneous networks. Specifically, we propose a fast algorithm based on the parallel computing scheme to obtain all node pairs with CN values larger than the lower bound. Furthermore, we propose a general measurement, called self-predictability, to quantify the performance of similarity indices in link prediction, which can also indicate the link predictability of networks with respect to given similarity indices. [ABSTRACT FROM AUTHOR]

The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple) graph G , find a maximum vertex subset S of G such that the subgraph induced by S satisfies a given property Π . Such problems were shown to be NP-hard in general if the properties considered are non-trivial and hereditary Lewis and Yannakakis (1980) and Yannakakis (1978). In this paper, using the augmenting graph technique, we describe a graph class, in which some problems can be solved in polynomial time. We also prove the NP-hardness of some Maximum Set problems where the considered properties are not hereditary. [ABSTRACT FROM AUTHOR]

This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids. [ABSTRACT FROM AUTHOR]

A many-to-many k -disjoint path cover ( k -DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T , each of size k , is a collection of k vertex-disjoint paths between S and T , which altogether cover every vertex of G . This is classified as paired , if each vertex of S must be joined to a specific vertex of T , or unpaired , if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired k - DPC problem on a unit interval graph is polynomially solvable for any fixed k . [ABSTRACT FROM AUTHOR]

In this paper, we deal with the problem of debugging and revision of incoherent terminologies. Ontology debugging aims to provide the explanation of the causes of incoherence and ontology revision aims to eliminate the incoherence. For this purpose, we propose the graph-based approaches to deal with the debugging and revision of terminologies for a family of lightweight ontology languages, DL-Lite. First of all, we transform DL-Lite ontologies to graphs. To deal with the problem of ontology debugging, we calculate the minimal incoherence-preserving subsets (MIPS) of an ontology by computing the minimal incoherence-preserving path-pairs (MIPP) based on the transformed graph. To deal with the problem of ontology revision, we propose the notion of revision state which separates the terminology of an ontology into two disjoint sets: the set of wanted axioms and the set of unwanted axioms. We further define a revision operator based on the revision state. Afterward, two revision algorithms are proposed to instantiate the revision operator: one is based on a scoring function, and the other one is based on a hitting set tree. We implement these algorithms and conduct experiments of ontology debugging and ontology revision on several adapted real ontologies. The experimental results of ontology debugging show that our approach of calculating MIPS based on graph is efficient and outperforms the state of the art. The experimental results of ontology revision show that the algorithm based on a scoring function is more efficient than the algorithm based on a hitting set tree. [ABSTRACT FROM AUTHOR]

Propagation source location is an important problem which can help authorities developing control strategies on complex networks. In this paper, we study this problem by assuming that there is a single propagation source and the spreading process on networks follows the Susceptible-Infected (SI) model. We define a Rationality Observation Value ( ROV ) on infected tree that has a fixed root and propose the corresponding measuring method. Using ROV , we construct a source estimator for tree graph and generalize it to arbitrary graph. Based on the generalized estimator, a novel Propagation Centrality (PC) algorithm is proposed, which could locate the propagation source on arbitrary graph with complexity O ( N 3 ). With PC algorithm, source location is converted into finding out a Breadth-First-Search (BFS) spanning tree with the maximal ROV from infected graph. We perform extensive simulations on a series of synthetic and real networks, the results show that PC performs better than other 5 existing methods. More importantly, the results also show that PC performs stable on the infected graph with sparse observation phenomenon. [ABSTRACT FROM AUTHOR]

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2 n 3 + 1 in 2-connected n -node solid grid graphs. [ABSTRACT FROM AUTHOR]

The scientific literature teems with clique-centric clustering strategies. In this paper we analyze one such method, the paraclique algorithm. Paraclique has found practical utility in a variety of application domains, and has been successfully employed to reduce the effects of noise. Nevertheless, its formal analysis and worst-case guarantees have remained elusive. We address this issue by deriving a series of lower bounds on paraclique densities. [ABSTRACT FROM AUTHOR]

Recently a delta-density based clustering (DDC) algorithm was proposed to cluster data efficiently by fast searching density peaks. In the DDC method, the density and a new-defined criterion delta-distance are utilized. The examples with anomalously large delta-density values are treated as cluster centers, then the remaining are assigned the same cluster label as their neighbor with higher density. However there are two challenges for the DDC algorithm. First, no rules are available to judge density-delta values as “anomalously large” or not. Second, the decision graph might produce the redundant examples with “anomalous large” density-delta values, as we define as the “decision graph fraud” problem. In this paper, an improved and automatic version of the DDC algorithm, named as 3DC clustering, is proposed to overcome those difficulties. The 3DC algorithm is motivated by the divide-and-conquer strategy and the density-reachable concept in the DBSCAN framework. It can automatically find the correct number of clusters in a recursive way. Experiments on artificial and real world data show that the 3DC clustering algorithm has a comparable performance with the supervised-clustering baselines and outperforms the unsupervised DDCs, which utilize the novelty detection strategies to select the “anomalously large” density-delta examples for cluster centers. [ABSTRACT FROM AUTHOR]

Learning-to-rank techniques have shown promising results in the domain of image ranking recently, where dimensionality reduction is a critical step to overcome the “curse of dimensionality”. However, conventional dimensionality reduction approaches cannot guarantee the satisfying performance because the important ranking information is ignored. This paper presents a novel “Ranking Dimensionality Reduction” scheme specifically designed for learning-to-rank based image ranking, which aims at not only discovering the intrinsic structure of data but also keeping the ordinal information. Within this scheme, a new dimensionality reduction algorithm called Relevance Marginal Fisher Analysis (RMFA) is proposed. RMFA models the proposed pairwise constraints of relevance-link and irrelevance-link into the relevance graph and the irrelevance graph, and applies the graphs to build the objective function with the idea of Marginal Fisher Analysis (MFA). Further, a semi-supervised RMFA algorithm called Semi-RMFA is developed to offer a more general solution for the real-world application. Extensive experiments are carried on two popular, real-world image search reranking datasets. The promising results demonstrate the robustness and effectiveness of the proposed scheme and methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the competition graphs of oriented complete bipartite graphs. We characterize graphs that can be represented as the competition graphs of oriented complete bipartite graphs. We also present the graphs having the maximum number of edges and the graphs having the minimum number of edges among such graphs. [ABSTRACT FROM AUTHOR]

The average eccentricity e c c ( G ) of a graph G is the mean value of eccentricities of all vertices of G . In this paper, we continue the work of Ilić (2012) and resolve a conjecture, obtained by the system AutoGraphiX, about the upper bound on the sum of the average eccentricity and the domination number among connected graphs on n vertices. [ABSTRACT FROM AUTHOR]

An r -dynamic k -coloring of a graph G is a proper vertex k -coloring of G such that the neighbors of any vertex v receive at least min { r , deg ( v ) } different colors. The r -dynamic chromatic number of G , χ r ( G ) , is defined as the smallest k such that G admits an r -dynamic k -coloring. In this paper, first we introduce an upper bound for χ r ( G ) in terms of r , chromatic number, maximum degree and minimum degree. Then, motivated by a conjecture of Montgomery (2001) stating that for a d -regular graph G , χ 2 ( G ) − χ ( G ) ≤ 2 , we prove two upper bounds for χ 2 − χ on regular graphs. Our first upper bound ⌈ 5.437 log d + 2.721 ⌉ improves a result of Alishahi (2011). Also, our second upper bound shows that Montgomery’s conjecture is implied by the existence of a χ ( G ) -coloring for any regular graph G , such that any two vertices whose neighbors are unicolored in this coloring, have no common neighbor. [ABSTRACT FROM AUTHOR]

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph B S n under the MM model is 6 n − 15 for n ≥ 6 and under the PMC model is 8 n − 21 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. [ABSTRACT FROM AUTHOR]

A subset F of vertices of a graph G is called a vertex cover P t ( V C P t ) set if every path of order t in G contains at least one vertex from F . The vertex cover P t ( V C P t ) problem is to find a minimum V C P t set in a graph. The V C P t problem is NP-complete for any integer t ≥ 2 . In this paper, we restrict our attention to the V C P 4 problem and present an FPT algorithm with runtime O ∗ ( 3 k ) for the V C P 4 problem. The algorithm constructs a V C P 4 set of size at most k in a given graph G , or reports that no such V C P 4 set exists in G . [ABSTRACT FROM AUTHOR]

Controllability of complex networks has been one of the attractive research areas for both network and control community, and has yielded many promising and significant results in minimum inputs and minimum driver vertices. However, few studies have been devoted to studying the minimum controlled vertex set through which control over the network with arbitrary structure can be achieved. In this paper, we prove that the minimum driver vertices driven by different inputs are not sufficient to ensure the full control of the network when the associated graph contains the inaccessible strongly connected component which has perfect matching and propose an algorithm to identify a minimum controlled vertex set for network with arbitrary structure using convenient graph and mathematical tools. And the simulation results show that the controllability of network is correlated to the number of inaccessible strongly connected components which have perfect matching and these results promote us to better understand the relationship between the network’s structural characteristics and its control. [ABSTRACT FROM AUTHOR]

Evaluation of image segmentation algorithms is a crucial task in the image processing field. Generally, traditional objective evaluation measures, such as ME and JS, always give the same treatment to the object pixels and the background pixels in images, which is not reasonable in practical applications. To overcome this problem, a new objective evaluation metric based on the weighted-ROC graph is proposed in this paper. Considering that pixels in different positions may gain different importance, each pixel is given a weight based on its spatial information. The ROC (receiver operating characteristic) graph with weighting strategy is constructed to evaluate the performance of segmentation algorithms quantitatively. The proposed metric focuses on the segmented objects, which is similar to human visual system. Meanwhile, it reserves the robustness of ROC against the region imbalance. The experimental results on various images show that the proposed metric gives more reasonable evaluation results than other metrics. [ABSTRACT FROM AUTHOR]

The topic of this paper is the retrieval of a particular object. A graph traversal-based re-ranking framework for the baseline bag-of-words (BOW) approach is proposed. For an image, we consider not only its similarity with the query image, but also the relationship between other dataset images. We integrate these information as image attributes via an extended image graph and propose a graph traversal algorithm to efficiently obtain their values. By comprehensively considering these attributes, we propose an attribute similarity measure for re-ranking, which brings much performance improvement. We further use our method for the multiple-query retrieval with a simple extension of the virtual query. The experimental results show that our method significantly improve the baseline approach and achieves competitive performance compared with the other state-of-the-art methods. Additionally, our re-ranking method requires only a little extra memory space and time costs. [ABSTRACT FROM AUTHOR]

For two positive integers m , k and a connected graph G = ( V , E ) with a nonnegative vertex weight function w , the balanced m -connected k -partition problem, denoted as BC m P k , is to find a partition of V into k disjoint nonempty vertex subsets ( V 1 , V 2 , … , V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m -connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G , k ) , that is, β m ⁎ ( G , k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) } , where the maximum is taken over all m -connected k -partition of G . In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2 , a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k , where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2 k -connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v . In the case that every vertex has weight at most W / k , we prove a lower bound β 2 ⁎ ( G , k ) ≥ W / ( 2 k − 1 ) for 2 k -connected interval graph G . (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2 k -connected interval graphs. [ABSTRACT FROM AUTHOR]

Anchorgraph based learning methods have met with success in modeling the large data for scalable semi-supervised learning. However, like most graph based learning algorithms, they are usually built with a randomly selected labeled set classified in advance. Although many pool-based active learning methods have been proposed, they often require a relatively large computational and storage consumption, which tends to impose extra burden on the learning system. Thus in this paper, we propose a novel active learning method named anchor-based transductive experimental design (ATED). By fully utilizing the representing power of anchors, the improved method efficiently enhances the performance of the original anchorgraph based learning while introduces much less extra cost on computation and storage. Extensive experimental results on real-world datasets have validated our approach in terms of classifying accuracy and computational efficiency. [ABSTRACT FROM AUTHOR]

The recent proliferation of videos has brought out the need for applications such as automatic annotation and organization . These applications could greatly benefit from the respective thematic content depending on the type of video. Unlike the other kinds of video, an advertising video usually conveys a specific theme in a certain time period (e.g. drawing the audience׳s attention to a product or emphasizing the brand). Traditional multi-label algorithms may not work effectively with advertising videos due mainly to their heterogeneous nature. In this paper, we propose a new learning paradigm to resolve the problems arising out of traditional multi-label learning in advertising videos through label relevance. Aiming to address the issue of label relevance, we firstly assign each label with label degree ( LD ) to classify all the labels into three groups such as first label ( FL ), important label ( IL ) and common label ( CL ), and then propose a Directed Probability Label Graph ( DPLG ) model to mine the most related labels from the multi-label data with label relevance, in which the interdependency between labels is considered. In the implementation of DPLG , the labels that appear occasionally and possess inconspicuous co-occurrences are consequently eliminated effectively, employing λ - filtering and τ - pruning processes, respectively. And then the graph theory is utilized in DPLG to acquire Correlative Label-Sets ( CLSs ). Lastly, the searched Correlative Label-Sets ( CLSs ) are utilized to enhance multi-label annotation. Experimental results on advertising videos and several publicly available datasets demonstrate the effectiveness of the proposed method for multi-label annotation with label relevance. [ABSTRACT FROM AUTHOR]

Online social networks are valuable sources of information to monitor real-time events, such as earthquakes and epidemics. For this type of surveillance, users’ location is an essential piece of information, but a substantial number of users choose not to disclose their geographical location. However, characteristics of the users׳ behavior, such as the friends they associate with and the types of messages published may hint on their spatial location. In this paper, we propose a method to infer the spatial location of Twitter users. Unlike the approaches proposed so far, it incorporates two sources of information to learn geographical position: the text posted by users and their friendship network. We propose a probabilistic approach that jointly models the geographical labels and Twitter texts of users organized in the form of a graph representing the friendship network. We use the Markov random field probability model to represent the network, and learning is carried out through a Markov Chain Monte Carlo simulation technique to approximate the posterior probability distribution of the missing geographical labels. We show the accuracy of the algorithm in a large dataset of Twitter users, where the ground truth is the location given by GPS. The method presents promising results, with little sensitivity to parameters and high values of precision. [ABSTRACT FROM AUTHOR]

Graph-based spectral clustering algorithms involve the analysis of an affinity matrix. The latter defines the pairwise similarity relations among data points. Popular graph partitioning algorithms typically involve a normalization step that reflects itself onto an affinity matrix normalization step in spectral clustering algorithms. In this paper, we show that affinity matrix normalization with constant row/column sum guarantees the invariance of the size-weighted sum of the between- and within-cluster graph association; a property conceptually equivalent to the data variance decomposition exploited by the standard k -means algorithm. From this observation, we demonstrate that the solution of numerous spectral clustering methods can be obtained using the standard graph ratio cut objective function. We have identified in the literature 7 such affinity matrix normalization schemes relevant to spectral clustering. Clustering experiments performed with these 7 normalization schemes on 17 benchmark datasets are presented. As a general rule, it is observed that the appropriate normalization method depends on the dataset. A geometric interpretation in the feature space (FS) of such a normalization scheme for k -way spectral clustering is also presented. [ABSTRACT FROM AUTHOR]

A total vertex irregularity strength of a graph G , tvs ( G ), is the minimum positive integer k such that there is a mapping f from the union of vertex and edge sets of G to {1, 2, · · ·, k } and the weights of all vertices are distinct. The weight of a vertex in G is the sum of its vertex label and the labels of all edges that incident to it. It is known that tvs ( Kn ) = 2. In this paper, we construct graphs with tvs equal to 2 by removing as much as possible edges from Kn , with and without maintaining the outer cycle Cn of Kn . To do so, we give two algorithms to construct the graphs, and show that the tvs of the resulting graph is equal to 2. [ABSTRACT FROM AUTHOR]

This paper presents three interconnected developments made during the course of a recent collective research work, the development of a systematic graph-based search tool for physical contradictions, a ranking approach for defining the order of criticality of the design contradictions and the associated analysis of the different design strategies that can be used to solve those contradictions or to enhance performance indicators. The systematic graph-based search for physical contradictions is using the set of elementary variables necessary to describe the system as basic input. The initial set is extracted based on taxonomy of variables combining classification work from NIST and classification of variables derived from the Bond Graph theory. The contradiction search method is in a second step classifying the set of variables into three categories: the constraint variables imposed to the designers by the context and the environment, the design variables on which the designer as the possibility to act and the performance variables that are used to evaluate the performance of the designed system. In a third step, interactions between variables are searched using two possibilities: a causal ordering algorithm developed during the course of the research or via a collective work of experts. The result of this step is a directed graph starting from the constraints variables and ending with the performance variables. In the fourth step objectives have to be assigned to the performance variables (minimal value, maximal value or target value). Those objectives are propagated back into the graph by analyzing the impact of the variables interacting with the performance variables. A physical contradiction is detected each time it is discovered that a design variable is associated with two contradictory objectives. Following this approach, a contradiction is represented as a node in the directed graph. It is possible to systematically map the different design strategies that can be used and to rank the possible impact of those design strategies. The article presents a concrete application of the approach on the case study of an air bearing and demonstrates the novelty of the approach to generate new viewpoints and insight in the analysis of the early stages of the development process. The potential impact of such type of design support is potentially very important. A future step will consists of developing a computer aided tool implementing the method. [ABSTRACT FROM AUTHOR]

In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph G ̃ , produces the directed Cartesian-product decomposition of G in linear time. This is the first time that the linear complexity is achieved for this problem, which has two major consequences. Firstly, it shows that the directed and undirected versions of the Cartesian-product decomposition of graphs are linear-time equivalent problems. And secondly, as there already exists a linear-time algorithm for solving the undirected version of the problem, combined together, it provides the first linear-time algorithm for computing the directed Cartesian-product decomposition of a directed graph. [ABSTRACT FROM AUTHOR]

Processing lineages (also called provenances) over uncertain data consists in tracing the origin of uncertainty based on the process of data production and evolution. In this paper, we focus on the representation and processing of lineages over uncertain data, where we adopt Bayesian network (BN), one of the popular and important probabilistic graphical models (PGMs), as the framework of uncertainty representation and inferences. Starting from the lineage expressed as Boolean formulae for SPJ (Selection–Projection–Join) queries over uncertain data, we propose a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee that the graphical model can support effective probabilistic inferences in lineage processing theoretically. Then, we propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. The BN for representing lineage expressions over uncertain data, called lineage BN and abbreviated as LBN, can be constructed while generally suitable for both safe and unsafe query plans. Therefore, we give the variable-elimination-based algorithm for LBN's exact inferences to obtain the probabilities of query results, called LBN-based query processing. Then, we focus on obtaining the probabilities of inputs or intermediate tuples conditioned on query results, called LBN-based inference query processing, and give the Gibbs-sampling-based algorithm for LBN's approximate inferences. Experimental results show the efficiency and effectiveness of our methods. [ABSTRACT FROM AUTHOR]

In this paper the influence of several factors to establish a suitable DMA design is considered using an adaptation of the methodology previously developed by Gomes [1] . This methodology is based on graph theory concepts (Floyd-Warshall algorithm) and some user-defined criteria to establish the number and size of DMAs and uses a Simulated Annealing algorithm to identify the most appropriate number and location of metering stations, boundary valves and network reinforcement/replacement needs along the project plan. Different design criteria are applied to a case study and the results obtained by the methodology are used to draw some conclusions. [ABSTRACT FROM AUTHOR]

The partitioning of water distribution system is a complex process achieved defining network clusters arranged in sectors, with the complete isolation of clusters through gate valves, or arranged in districts, inserting both gate valves and flow meters. The process is generally subdivided in two phases: clustering, aimed to define the shape and dimension of network clusters, and partitioning, aimed to select pipes in which to insert flow meters or gate valves. In this paper, different clustering procedures based on social network community detection and on graph partitioning algorithms, were compared using a real water system and a large battery of performance indices. [ABSTRACT FROM AUTHOR]

Hydraulic resilience can be formulated as a measure of the ability of a water distribution network to maintain a minimum level of service under operational and failure conditions. This paper explores a hybrid approach to bridge the gap between graph-theoretic and hydraulic measures of resilience. We extend the concept of geodesic distance of a pipeline by taking into account energy losses associated with flow. New random-walk algorithms evaluate hydraulically feasible routes and identify nodes with di ff erent levels of hydraulic resilience. The nodes with the lowest scores are further analysed by considering the availability and capacity of their supply routes. [ABSTRACT FROM AUTHOR]

Collective classification (CC) is a task to jointly classifying related instances of network data. Enabling CC usually improves the performance of predictive models on fully-labeled training networks with large amount of labeled data. However, acquiring such labels can be difficult and costly, and learning a CC classifier with only a few labeled data can lead to poor performance. On the other hand, there are usually large amount of unlabeled data available in practical. This naturally motivates semi-supervised collective classification (SSCC) approaches for leveraging the unlabeled data to improve CC from a sparsely-labeled network. In this paper, we propose a novel non-negative matrix factorization (NMF) based SSCC algorithm, called NMF-SSCC, to effectively learn a data representation by exploiting both labeled and unlabeled data on the network. Our idea is to use matrix factorization to obtain a compact representation of network data which uncovers the class discrimination of the data inferred from the labeled instances and simultaneously respects the intrinsic network structure. To achieve this, we design a new matrix factorization objective function and incorporate a label matrix factorization term as well as a network regularization term into it. An efficient optimization algorithm using the multiplicative updating rules is then developed to solve the new objective function. To further boost the predicting performance, we extend the proposed NMF-SSCC method into an ensemble scheme, called NMFE-SSCC, in terms of building a classification ensemble with a set of NMF-SSCC collective classifiers using different constructed latent graphs. Each NMF-SSCC classifier is learnt from one latent graph generated with various latent linkages for effectively label propagation. Experimental results on real-world data sets have demonstrated the effectiveness of the new methods. [ABSTRACT FROM AUTHOR]

In this paper, an efficient feature extraction algorithm called discriminant sparse local spline embedding (D-SLSE) is proposed for face recognition. A sparse neighborhood graph of the input data is firstly constructed based on a sparse representation framework, and then the low-dimensional embedding of the data is obtained by faithfully preserving the intrinsic geometry of the data samples based on such sparse neighborhood graph and best holding the discriminant power based on the class information of the input data. Finally, an orthogonalization procedure is perfomred to improve discriminant power. The experimental results on the two face image databases demonstrate that D-SLSE is effective for face recognition. [ABSTRACT FROM AUTHOR]

Given two positive integers l and m , with l ≤ m , an [ l , m ] - covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l ≤ | M | ≤ m for every M ∈ M . An [ l , m ] -covering M of G is an excessive [ l , m ] - factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [ l , m ] -factorization of G (or ∞ , if G does not admit an excessive [ l , m ] -factorization) is a graph parameter called the excessive [ l , m ] - index of G and denoted by χ [ l , m ] ′ ( G ) . In this paper we study such parameter. Our main result is a general formula for the excessive [ l , m ] -index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ [ l , m ] ′ ( G ) for any fixed constants l and m and outputs an excessive [ l , m ] -factorization of G , whenever the latter exists. [ABSTRACT FROM AUTHOR]

Detecting communities is significant to understand the potential structures and functions of complex systems. In order to detect communities more accurately and reasonably, a novel algorithm is proposed based on cosine distance and core-node in this paper. Cosine distances between nodes are regarded as their similarity measure and network node vectors can be extracted directly from the similarity matrix without calculating eigenvectors. Core-nodes as the initial communities are found by cosine distance threshold and degree threshold. Furthermore, the initial communities are expanded by adding other nodes with the nearest cosine distance to core-nodes. Through changing degree and cosine distance thresholds constantly, the optimal community structure of complex networks can be obtained by optimizing modularity with high accuracy. Experimental results on both real-world and synthetic networks demonstrate the feasibility and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an integral (and fractional) packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m + n 3 + r branchings that makes at most m ( m + n 3 + r ) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. Leston-Rey and Wakabayashi described an algorithm that returns a packing with at most m + r − 1 branchings but makes a large number of oracle calls. In this work we provide an algorithm, inspired on ideas of Schrijver and in a paper of Gabow and Manu, that returns a packing with at most m + r − 1 branchings and makes at most ( m + r + 2 ) n oracle calls. Moreover, for the arborescence packing problem our algorithm provides a packing with at most m − n + 2 arborescences–thus improving the bound of m of Leston-Rey and Wakabayashi–and makes at most ( m − n + 5 ) n oracle calls. [ABSTRACT FROM AUTHOR]

Suppose that we are given two independent sets I b and I r of a graph such that | I b | = | I r | , and imagine that a token is placed on each vertex in I b . Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I b into I r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I b and I r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. [ABSTRACT FROM AUTHOR]

Feature selection techniques are attracting more and more attention with the growing number of domains that produce high dimensional data. Due to the absence of class labels, many researchers focus on the unsupervised scenario, attempting to find an optimal feature subset that preserves the original data distribution. However, the existing methods either fail to achieve sparsity or ignore the potential redundancy among features. In this paper, we propose a novel unsupervised feature selection algorithm, which retains the preserving power, and implements high sparsity and low redundancy in a unified manner. On the one hand, to preserve the data structure of the whole feature set, we build the graph Laplacian matrix and learn the pseudo class labels through spectral analysis. By finding a feature weight matrix, we are allowed to map the original data into a low dimensional space based on the pseudo labels. On the other hand, to ensure the sparsity and low redundancy simultaneously, we introduce a novel regularization term into the objective function with the nonnegative constraints imposed, which can be viewed as the combination of the matrix norms | | · | | m 1 and | | · | | m 2 on the weights of features. An iterative multiplicative algorithm is accordingly designed with proved convergence to efficiently solve the constrained optimization problem. Extensive experimental results on different real world data sets demonstrate the promising performance of our proposed method over the state-of-the-arts. [ABSTRACT FROM AUTHOR]

This paper presents a systematic pathway for the floor plan design when given the shape of required floor plan, the list of spaces, the dimensions of each space and the weighted matrix of required adjacencies between the spaces. The first step is to partition the given shape into say k possible rectangles. Then using the given adjacencies, divide the given spaces into k groups. Next is to construct a rectangular block for each group and at last adjoin all rectangular blocks to have the required floor plan. The obtained rectangular blocks are one of the best arrangement of spaces inside a rectangle from the point of view of connectivity. [ABSTRACT FROM AUTHOR]

A dominating induced matching , also called an efficient edge domination , of a graph G = ( V , E ) with n = | V | vertices and m = | E | edges is a subset F ⊆ E of edges in the graph such that no two edges in F share a common endpoint and each edge in E ∖ F is incident with exactly one edge in F . It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.146 7 n n O ( 1 ) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F , where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph). After giving several structural properties of the problem, we show that the problem always contains some “good vertices,” branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. [ABSTRACT FROM AUTHOR]

The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique challenges in the areas of (1) software complexity, (2) data complexity, (3) security, (4) mathematical complexity, (5) theoretical analysis, (6) serial performance, and (7) parallel performance. Implementing graph algorithms using matrix-based approaches provides a number of promising solutions to these challenges. The GraphBLAS standard ( istc-bigdata.org/GraphBlas ) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. The GraphBLAS mathematically defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the GraphBLAS and describes how the GraphBLAS can be used to address many of the challenges associated with analysis of graphs. [ABSTRACT FROM AUTHOR]