Search

Given a real number α ∈ (0 , 1) , we define the Webster sequence of density α to be W α = (⌈ (n − 1 / 2) / α ⌉) n ∈ N , where ⌈ x ⌉ is the ceiling function. It is known that if α and β are irrational with α + β = 1 , then W α and W β partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W α , W β , W γ with α , β , γ irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities α , β , γ. We show that if α , β , γ are irrational with α + β + γ = 1 , there exists a partition of N into sequences of densities α , β , γ , in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the n th element of each sequence in O (1) time and the second algorithm gives the assignment of the m th positive integer to a sequence in O (1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. [ABSTRACT FROM AUTHOR]

Semantic segmentation has been a major topic in research and industry in recent years. However, due to the computation complexity of pixel-wise prediction and backpropagation algorithm, semantic segmentation has been demanding in computation resources, resulting in slow training and inference speed and large storage space to store models. Existing schemes that speed up segmentation network change the network structure and come with noticeable accuracy degradation. However, neural network quantization can be used to reduce computation load while maintaining comparable accuracy and original network structure. Semantic segmentation networks are different from traditional deep convolutional neural networks (DCNNs) in many ways, and this topic has not been thoroughly explored in existing works. In this paper, we propose a new quantization framework for training and inference of segmentation networks, where parameters and operations are constrained to 8-bit integer-based values for the first time. Full quantization of the data flow and the removal of square and root operations in batch normalization give our framework the ability to perform inference on fixed-point devices. Our proposed framework is evaluated on mainstream semantic segmentation networks like FCN-VGG16 and DeepLabv3-ResNet50, achieving comparable accuracy against floating-point framework on ADE20K dataset and PASCAL VOC 2012 dataset. [ABSTRACT FROM AUTHOR]

Every square matrix A = (a u v) ∈ C n × n can be represented as a digraph having n vertices. In the digraph, a block (or 2-connected component) is a maximally connected subdigraph that has no cut-vertex. The determinant and the permanent of a matrix can be calculated in terms of the determinant and the permanent of some specific induced subdigraphs of the blocks in the digraph. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Such partitions of the digraph are called the B -partitions. In this paper, first, we develop an algorithm to find the B -partitions. Next, we analyze the parameterized complexity of matrix determinant and permanent, where, the parameters are the sizes of blocks and the number of cut-vertices of the digraph. We give a class of combinations of cut-vertices and block sizes for which the parametrized complexities beat the state of art complexities of the determinant and the permanent. [ABSTRACT FROM AUTHOR]

In the first part of this paper, we present a method to build affinity matrices for spectral clustering from a density estimator relying on K-means with subbagging procedure. The approach is anchored in the theoretical works of Wong (1980, 1982a, b) [13–15] on the asymptotic properties of K-means as a density estimation method. The subbagging procedure is introduced to improve the density estimate accuracy. The behavior of the proposed method is analyzed on diverse data sets and two new mechanisms are suggested to improve clustering results on non-convex data. In the second part of the paper, we establish a link between the presented method and the evidence accumulation clustering (EAC) approach by showing that a normalized version of the density-based similarity matrix is approximately equal to a normalized version of the co-association matrix. The co-association matrix provides the co-occurrence probability of data pairs assigned to a same cluster over multiple K-means clustering partitions. Experimental results on artificial and real data demonstrate the effectiveness of the method and provide empirical support for the established link. [ABSTRACT FROM AUTHOR]

Like clustering analysis, community detection aims at assigning nodes in a network into different communities. Fdp is a recently proposed density-based clustering algorithm which does not need the number of clusters as prior input and the result is insensitive to its parameter. However, Fdp cannot be directly applied to community detection due to its inability to recognize the community centers in the network. To solve the problem, a new community detection method (named IsoFdp) is proposed in this paper. First, we use IsoMap technique to map the network data into a low dimensional manifold which can reveal diverse pair-wised similarity. Then Fdp is applied to detect the communities in the network. An improved partition density function is proposed to select the proper number of communities automatically. We test our method on both synthetic and real-world networks, and the results demonstrate the effectiveness of our algorithm over the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Abstract: The detection of overlapping community structure in networks can give insight into the structures and functions of many complex systems. In this paper, we propose a simple but efficient overlapping community detection method for very large real-world networks. Taking a high-quality, non-overlapping partition generated by existing, efficient, non-overlapping community detection methods as input, our method identifies overlapping nodes between each pair of connected non-overlapping communities in turn. Through our analysis on modularity, we deduce that, to become an overlapping node without demolishing modularity, nodes should satisfy a specific condition presented in this paper. The proposed algorithm outputs high quality overlapping communities by efficiently identifying overlapping nodes that satisfy the above condition. Experiments on synthetic and real-world networks show that in most cases our method is better than other algorithms either in the quality of results or the computational performance. In some cases, our method is the only one that can produce overlapping communities in the very large real-world networks used in the experiments. [Copyright &y& Elsevier]

Abstract: Co-association matrix has been a useful tool in many clustering ensemble techniques as a similarity measure between objects. In this paper, we introduce the weighted-association matrix, which is more expressive than the traditional co-association as a similarity measure, in the sense that it integrates information from the set of partitions in the clustering ensemble as well as from the original data of object representations. The weighted-association matrix is the core of the two main contributions of this paper: a natural extension of the well-known evidence accumulation cluster ensemble method by using the weighted-association matrix and a kernel based clustering ensemble method that uses a new data representation. These methods are compared with simple clustering algorithms as well as with other clustering ensemble algorithms on several datasets. The obtained results ratify the accuracy of the proposed algorithms. [Copyright &y& Elsevier]

Abstract: Hardware/software (HW/SW) partitioning is one of the crucial steps of co-design systems. It determines which components of the systems are implemented in hardware and which ones are in software. In this paper the computing model is extended to cater for the path-based HW/SW partitioning with the fine granularity in which communication penalties between system components must be considered. On the new computing model an efficient heuristic algorithm is developed, in which both speedup in hardware and communication penalty are taken into account. In addition, an efficient tabu search algorithm is also customized in this paper to refine the approximate solutions produced by the heuristic algorithm. Simulation results show that the heuristic algorithm runs fast and is able to produce high-quality approximate solutions. Moreover, the tabu search algorithm can further refine them to nearly optimal solutions within an acceptable runtime. The difference between the approximate solutions and the optimal ones is bounded by 0.5%, and it hardly increases with the increase of the problem size. [Copyright &y& Elsevier]

Abstract: This paper presents the colored farthest-neighbor graph (CFNG), a new method for finding clusters of similar objects. The method is useful because it works for both objects with coordinates and for objects without coordinates. The only requirement is that the distance between any two objects be computable. In other words, the objects must belong to a metric space. The CFNG uses graph coloring to improve on an existing technique by Rovetta and Masulli. Just as with their technique, it uses recursive partitioning to build a hierarchy of clusters. In recursive partitioning, clusters are sometimes split prematurely, and one of the contributions of this paper is a way to reduce the occurrence of such premature splits, which also result when other partition methods are used to find clusters. [Copyright &y& Elsevier]

Abstract: The recursive method for computing the generalized LM-inverse of a constant rectangular matrix augmented by a column vector is proposed in Udwadia and Phohomsiri (2007) . The corresponding algorithm for the sequential determination of the generalized LM-inverse is established in the present paper. We prove that the introduced algorithm for computing the generalized LM-inverse and the algorithm for the computation of the weighted Moore–Penrose inverse developed by Wang and Chen (1986) in are equivalent algorithms. Both of the algorithms are implemented in the present paper using the package MATHEMATICA. Several rational test matrices and randomly generated constant matrices are tested and the CPU time is compared and discussed. [Copyright &y& Elsevier]

Abstract: This paper reviews and extends a technique to detect weak coupling (one-way coupling or complete decoupling) among elements of a dynamic system model, and to partition and reduce models in which weak coupling is found. The ability to partition a model increases the potential for physical-domain model reduction, and allows parallel simulation of smaller individual submodels that can reduce computation time. Negligible constraint equation terms are identified and eliminated in a bond graph by converting inactive power bonds to modulated sources. If separate bond graphs result, between which all modulating signals move from a “driving” subgraph to a “driven” one, then one-way coupling exists in the model and it can be separated into driving and driven partitions. Information flow between the subgraphs is one-way. In this paper the algorithm is extended to models in which two-way information flow from modulating signals precludes complete partitioning. It is shown for several classes of modulating signals that, under certain conditions the signal is “weak” and therefore can be eliminated. Removal of weak signals allows partitioning of the longitudinal and pitch dynamics of a medium-duty truck model. The intensity of dynamic coupling and the potential for model reduction are shown to depend on the magnitude of system parameters and the severity of inputs such as road roughness. [Copyright &y& Elsevier]

Abstract: Let be a planar graph with vertices and with a partition of the vertex set into subsets for some positive integer . Let be a set of distinct points in the plane with a partition into subsets with (). This paper studies the problem of computing a planar polyline drawing of , such that each vertex of is mapped to a distinct point of . Lower and upper bounds on the number of bends per edge are proved for any . In the special case , we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717–728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. [Copyright &y& Elsevier]

Abstract: We consider the problem of reconstructing a partition x of the integer n from the set of its t-subpartitions. These are the partitions of the integer obtained by deleting a total of t from the parts of x in all possible ways. It was shown (in a forthcoming paper) that all partitions of n can be reconstructed from t-subpartitions if n is sufficiently large in relation to t. In this paper we deal with efficient reconstruction, in the following sense: if all partitions of n are -reconstructible, what is the minimum number such that every partition of n can be identified from any distinct subpartitions? We determine the function and describe the corresponding algorithm for reconstruction. Superpartitions may be defined in a similar fashion and we determine also the maximum number of t-superpartitions common to two distinct partitions of n. [Copyright &y& Elsevier]

In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O ( k 6 ) . [ABSTRACT FROM AUTHOR]

Inspired by the dynamics phenomenon occurred in social networks, the WJJLGS model is modified to imitate the clustering dynamics of signed social networks. Analyses show that the clustering dynamics of the model can be applied to partition signed social networks. Traditionally, blockmodel is applied to partition signed networks. In this paper, a detailed dynamics-based algorithm for signed social networks (DBAS) is presented. Simulations on several typical real-world and illustrative networks that have been analyzed by the blockmodel verify the correctness of the proposed algorithm. The efficiency of the algorithm is verified on large scale synthetic networks. [ABSTRACT FROM AUTHOR]

Community structure detection algorithm is employed in a vast amount of study to partition a network into some loosely coupled sub-networks of smaller scale. It is an effective tool to analyze and control some large-scale networks such as power grids. This paper proposes a novel algorithm based on local similarity to detect the community structure in complex network. Firstly, a new similarity index between nodes is defined to model the topological closeness of local connections in networks. Then nodes sharing high similarity are gathered to form the community structure. The results suggest the emergence of the bridging nodes and kernels within the community detection process. This proposed method performs well when it is introduced to seek out the actual community structure, kernels and bridging nodes in some benchmark networks. Thirdly, the proposed algorithm lends itself to many applications, such as detecting communities in several IEEE standard power grids and investigating the roles of bridging nodes in cascading failures. Experimentally, the proposed algorithm outperforms some other similarity indices and clustering methods. Finally, a detailed comparison helps us get the conclusion that the traditional label propagation algorithm is a special case of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u 1 and u 2 in a large directed graph G, we check the existence of a directed path from u 1 to u 2, where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by re-defining the “distance” of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method. [Copyright &y& Elsevier]

Abstract: In this paper, a new block preconditioner is proposed for the block partitioned matrices. This preconditioner is based on the block C-orthogonalization, where C is a symmetric positive definite matrix. The block preconditioned least squares (BPLS) and block preconditioned global least squares (BPGLS) algorithms are presented to solve the linear system of equations with block partioned coefficient matrix and multiple linear system of equations, respectively. The BPLS algorithm is applied to solve the complex linear system of equations and also BPLS and classical preconditioned least squares (PLS) algorithms are compared. Finally, some numerical experiments are given to show the efficiency of the new block preconditioner. [Copyright &y& Elsevier]

Abstract: A graph is a unipolar graph if there exists a partition such that is a clique and induces the disjoint union of cliques. The complement-closed class of generalized split graphs contains those graphs such that either or the complement of is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all -free (and hence, almost all perfect graphs) are generalized split graphs. In this paper, we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time , where is the number of edges added in a minimal triangulation of the given graph. Generalized split graphs can be recognized via this algorithm in time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in time, and for finding a maximum clique and a minimum proper coloring in time, when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bounds. We also report that the perfect code problem is NP-complete for chordal unipolar graphs. [Copyright &y& Elsevier]

Abstract: Let be a graph on vertices. We call a subset of the vertex set -small if, for every vertex , . A subset is called -large if, for every vertex , . Moreover, we denote by the minimum integer such that there is a partition of into -small sets, and by the minimum integer such that there is a partition of into -large sets. In this paper, we will show tight connections between -small sets, respectively -large sets, and the -independence number, the clique number and the chromatic number of a graph. We shall develop greedy algorithms to compute in linear time both and and prove various sharp inequalities concerning these parameters, which we will use to obtain refinements of the Caro–Wei Theorem, Turán’s Theorem and the Hansen–Zheng Theorem among other things. [Copyright &y& Elsevier]

Abstract: This paper considers the problem of clustering the vertices of a complete edge-weighted graph. The objective is to maximize the sum of the edge weights within the clusters (also called cliques). This so-called Clique Partitioning Problem (CPP) is NP-complete, and has several real-life applications such as groupings in flexible manufacturing systems, in biology, in flight gate assignment, etc. Numerous heuristics and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from the literature, improve the constraint propagation techniques for fixing edges in each node, and present a new branching scheme. The theoretical improvements are reflected by computational tests with real-life data. Although a standard solver delivers best results on randomly generated data, the runtime of the proposed algorithm is very low when being applied to instances on object clustering. [Copyright &y& Elsevier]

Abstract: Given a positive integer and an undirected edge-weighted connected simple graph with at least edges of positive weight, we wish to partition the graph into edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible. [Copyright &y& Elsevier]

Abstract: This paper presents a novel technique for recognizing broken characters found in degraded text documents by modeling it as a set-partitioning problem (SPP). The proposed technique searches for the optimal set-partition of the connected components by which each subset yields a reconstructed character. Given the non-linear nature of the objective function needed for optimal set-partitioning, we design an algorithm that we call Heuristic Incremental Integer Programming (HIIP). The algorithm employs integer programming (IP) with an incremental approach using heuristics to hasten the convergence. The objective function is formulated as probability functions that reflect common OCR measurements – pattern resemblance, sizing conformity and distance between connected components. We applied the HIIP technique to Thai and English degraded text documents and achieved accuracy rates over 90%. We also compared HIIP against three competing algorithms and achieved higher comparative accuracy in each case. [Copyright &y& Elsevier]

Abstract: Determining community structure in networks is fundamental to the analysis of the structural and functional properties of those networks, including social networks, computer networks, and biological networks. Modularity function , which was proposed by Newman and Girvan, was once the most widely used criterion for evaluating the partition of a network into communities. However, modularity is subject to a serious resolution limit. In this paper, we propose a new function for evaluating the partition of a network into communities. This is called community coefficient . Using community coefficient , we can automatically identify the ideal number of communities in the network, without any prior knowledge. We demonstrate that community coefficient is superior to the modularity and does not have a resolution limit. We also compared the two widely used community structure partitioning methods, the hierarchical partitioning algorithm and the normalized cuts (Ncut) spectral partitioning algorithm. We tested these methods on computer-generated networks and real-world networks whose community structures were already known. The Ncut algorithm and community coefficient were found to produce better results than hierarchical algorithms. Unlike several other community detection methods, the proposed method effectively partitioned the networks into different community structures and indicated the correct number of communities. [Copyright &y& Elsevier]

Abstract: Association rule mining (ARM) is one of the popular data mining methods that discover interesting correlations amongst a large collection of data, which appears incomprehensible. This is known to be a trivial task when the data is owned by one party. But when multiple data sites collectively engage in ARM, privacy concerns are introduced. Due to this concern, privacy preserving data mining algorithms have been developed to attain the desired result, while maintaining privacy. In the case of two party privacy preserving ARM for horizontally partitioned databases, both parties are required to compare their itemset counts securely. This problem is comparable to the famous millionaire problem of Yao. However, in this paper, we propose a secure comparison technique using fully homomorphic encryption scheme that provides a similar level of security to the Yao based solution, but promotes greater efficiency due to the reuse of resources. [Copyright &y& Elsevier]

Abstract: A matrix with nonnegative integer entries is minimal if the nonincreasing sequence of its entries (called -sequence) is minimal, in the dominance order of partitions, among all nonincreasing sequences of entries of matrices with nonnegative integers that have the same 1-marginals as . The starting point for this work is an identity that relates the number of minimal matrices that have fixed 1-marginals and -sequence to a linear combination of Kronecker coefficients. In this paper we provide a bijection that realizes combinatorially this identity. From this bijection we obtain an algorithm that to each minimal matrix associates a minimal component, with respect to the dominance order, in a Kronecker product, and a combinatorial description of the corresponding Kronecker coefficient in terms of minimal matrices and tableau insertion. Our bijection follows from a generalization of the dual RSK correspondence to 3-dimensional binary matrices, which we state and prove. With the same tools we also obtain a generalization of the RSK correspondence to 3-dimensional integer matrices. [Copyright &y& Elsevier]

Abstract: The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments (Filkov and Skiena (2004a,b) . The problem asks for a partition that summarizes a set of input partitions (each corresponding to a different microarray experiment) under a simple and intuitive cost. The problem on instances with two input partitions has a simple polynomial time algorithm, but it becomes APX-hard on instances with three input partitions. The quest for defining the boundary between tractable and intractable instances leads to the investigation of the restriction of Consensus Clustering when the output partition contains a fixed number of sets. In this paper, we give a randomized polynomial time approximation scheme for such problems, while proving its NP-hardness even for 2 output partitions, therefore definitively settling the approximation complexity of the problem. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a new region-based active contour model (ACM) for image segmentation. In particular, this model utilizes an improved region fitting term to partition the regions of interests in images depending on the local statistics regarding the intensity and the magnitude of gradient in the neighborhood of a contour. By this improved region fitting term, images with noise, intensity non-uniformity, and low-contrast boundaries can be well segmented. Integrated with the duality theory and the anisotropic diffusion process based on structure tensor, a new regularization term is defined through the duality formulation to penalize the length of active contour. By this new regularization term, the structural information of images is utilized to improve the ability of capturing the geometric features such as corners and cusps. From a numerical point of view, we minimize the energy function of our model by an efficient dual algorithm, which avoids the instability and the non-differentiability of traditional numerical solutions, e.g. the gradient descent method. Experiments on medical and natural images demonstrate the advantages of the proposed model over other segmentation models in terms of both efficiency and accuracy. [Copyright &y& Elsevier]

Abstract: In this paper, a covariance-free iterative algorithm is developed to achieve distributed principal component analysis on high-dimensional data sets that are vertically partitioned. We have proved that our iterative algorithm converges monotonously with an exponential rate. Different from existing techniques that aim at approximating the global PCA, our covariance-free iterative distributed PCA (CIDPCA) algorithm can estimate the principal components directly without computing the sample covariance matrix. Therefore a significant reduction on transmission costs can be achieved. Furthermore, in comparison to existing distributed PCA techniques, CIDPCA can provide more accurate estimations of the principal components and classification results. We have demonstrated the superior performance of CIDPCA through the studies of multiple real-world data sets. [Copyright &y& Elsevier]

Abstract: Given a search space , an unknown element and fixed integers and , a -ary -restricted query is of the following form: which one of the set is the in?, where is a partition of and for . The problem of finding from with -ary size-restricted queries is called as a -ary search game with small sets. In this paper, we consider sequential algorithms for the above problem, and establish the minimum number of average-case sequential queries when satisfies the uniform distribution on . [Copyright &y& Elsevier]

Abstract: Given the features obtained from a sequence of consecutively acquired sensor readings, this paper proposes an on-line algorithm for unsupervisedly detecting a transition on this sequence, i.e. the frame that divides the sequence into two tightly related parts that are dissimilar between them. Contrary to recently proposed approaches that address this partitioning problem dealing with a sequence of robot’s poses, our proposal considers each individual feature as a node of an incrementally built graph whose edges link two nodes if their associated features were simultaneously observed. These graph edges carry non-negative weights according to the locality of the features. Given a feature, its locality defines the set of features that has been observed simultaneously with it at least once. At each execution of the algorithm, the feature-based graph is split into two subgraphs using a normalized spectral clustering algorithm. The obtained partitions correspond to those parts in the environment that share the minimum amount of information. If this graph partition is validated, the algorithm determines that there is a significant change on the perceived scenario, assuming that a transition area has been traversed. In a map partitioning framework, we have tested the proposed approach in real environments where features are obtained using 2D laser sensors or vision (stereo and monocular cameras). The statistical evaluation of the experimental results demonstrates the performance of the proposal. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a novel Fast Affinity Propagation clustering approach (FAP). FAP simultaneously considers both local and global structure information contained in datasets, and is a high-quality multilevel graph partitioning method that can implement both vector-based and graph-based clustering. First, a new Fast Sampling algorithm (FS) is proposed to coarsen the input sparse graph and choose a small number of final representative exemplars. Then a density-weighted spectral clustering method is presented to partition those exemplars on the global underlying structure of data manifold. Finally, the cluster assignments of all data points can be achieved through their corresponding representative exemplars. Experimental results on two synthetic datasets and many real-world datasets show that our algorithm outperforms the state-of-the-art original affinity propagation and spectral clustering algorithms in terms of speed, memory usage, and quality on both vector-based and graph-based clustering. [Copyright &y& Elsevier]

Abstract: This paper introduces hard clustering algorithms that are able to partition objects taking into account simultaneously their relational descriptions given by multiple dissimilarity matrices. These matrices have been generated using different sets of variables and dissimilarity functions. These methods are designed to furnish a partition and a prototype for each cluster as well as to learn a relevance weight for each dissimilarity matrix by optimizing an adequacy criterion that measures the fitting between the clusters and their representatives. These relevance weights change at each algorithm iteration and can either be the same for all clusters or different from one cluster to another. Experiments with data sets (synthetic and from UCI machine learning repository) described by real-valued variables as well as with time trajectory data sets show the usefulness of the proposed algorithms. [Copyright &y& Elsevier]

Abstract: This paper presents a fast simulated annealing framework for combining multiple clusterings based on agreement measures between partitions, which are originally used to evaluate a clustering algorithm. Although we can follow a greedy strategy to optimize these measures as the objective functions of clustering ensemble, it may suffer from local convergence and simultaneously incur too large computational cost. To avoid local optima, we consider a simulated annealing optimization scheme that operates through single label changes. Moreover, for the measures between partitions based on the relationship (joined or separated) of pairs of objects, we can update them incrementally for each label change, which ensures that our optimization scheme is computationally feasible. The experimental evaluations demonstrate that the proposed framework can achieve promising results. [Copyright &y& Elsevier]

Abstract: The validity index has been used to evaluate the fitness of partitions produced by clustering algorithms for points in Euclidean space. In this paper, we propose a new validity index for network partitions, which can provide a measure of goodness for the community structure of networks. It is defined as a product of two factors, and involves the compactness and separation for each partition. The simulated annealing strategy is used to minimize such a validity index function in coordination with our previous -means algorithm based on the optimal reduction of a random walker Markovian dynamics on the network. It is demonstrated that the algorithm can efficiently find the community structure during the cooling process. The number of communities can be automatically determined without any prior knowledge of the community structure. Moreover, the algorithm is successfully applied to three real-world networks. [Copyright &y& Elsevier]

Abstract: This paper presents the design of a new clustering algorithm for images having wide range of variations in appearances and shape. The major chore of the clustering process involves in creating the partitions, reassigning the elements of the partitions and identifying the compact cluster obtained. The clusters are created from various low-dimensional spaces of the data set. Hierarchically related eigenspaces are employed to reassign the elements of the cluster. The clusters obtained from the proposed clustering scheme are used to form the learning set of the classification module. The quality of clusters generated is evaluated from the classification results. Comparisons on the clustering performance have been made with the well-known K-means and nearest neighbor-based clustering techniques. Excellent performance of the proposed clustering scheme is proved from the results reported. The benchmark datasets for objects and faces having images with large pose variations have been used to illustrate the efficiency and effectiveness of the proposed scheme. [Copyright &y& Elsevier]

Abstract: In this paper, a partitioning approach for large-scale systems based on graph-theory is presented. The algorithm starts with the translation of the system model into a graph representation. Once the system graph is obtained, the problem of graph partitioning is then solved. The resultant partition consists in a set of non-overlapping subgraphs whose number of vertices is as similar as possible and the number of interconnecting edges between them is minimal. To achieve this goal, the proposed algorithm applies a set of procedures based on identifying the highly connected subgraphs with balanced number of internal and external connections. In order to illustrate the use and application of the proposed partitioning approach, it is used to decompose a dynamical model of the Barcelona drinking water network (DWN). Moreover, a hierarchical-like DMPC strategy is designed and applied over the resultant set of partitions in order to assess the closed-loop performance. Results obtained when used several simulation scenarios show the effectiveness of both the partitioning approach and the DMPC strategy in terms of the reduced computational burden and, at the same time, of the admissible loss of performance in contrast to a centralised MPC strategy. [Copyright &y& Elsevier]

Abstract: Clarkson''s algorithm is a three-staged randomized algorithm for solving linear programs. This algorithm has been simplified and adapted to fit the framework of LP-type problems. In this framework we can tackle a number of non-linear problems such as computing the smallest enclosing ball of a set of points in . In 2006, it has been shown that the algorithm in its original form works for violator spaces too, which are a proper generalization of LP-type problems. It was not clear, however, whether previous simplifications of the algorithm carry over to the new setting. In this paper we show the following theoretical results: (a) It is shown, for the first time, that Clarkson''s second stage can be simplified. (b) The previous simplifications of Clarkson''s first stage carry over to the violator space setting. (c) The equivalence of violator spaces and partitions of the hypercube by hypercubes. [Copyright &y& Elsevier]

Abstract: This paper presents a fully coupled three-dimensional solver for the analysis of time-dependent fluid–structure interaction. A partitioned time marching algorithm is employed for the solution of the time-dependent coupled discretised problem, enabling the use of highly developed, robust and well-tested solvers for each field. Conservative transfer of information at the fluid–structure interface is combined with an effective block-Gauss–Seidel iterative scheme to enable implicit coupling of the interacting fields at each time increment. The three-dimensional unsteady incompressible fluid is solved using a powerful implicit dual time stepping technique with explicit multi-stage Runga–Kutta time stepping in pseudo-time and an ALE formulation for moving boundaries. A finite element dynamic analysis of the highly deformable structure is carried out with a numerical strategy combining the implicit Newmark time integration algorithm with a Newton–Raphson second-order optimisation method. Test cases are presented to benchmark the algorithm and to demonstrate the potential applications of this method. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a new method named MSSE-PSO (master–slave swarms shuffling evolution algorithm based on particle swarm optimization) is proposed. Firstly, a population of points is sampled randomly from the feasible space, and then partitioned into several sub-swarms (one master swarm and other slave swarms). Each slave swarm independently executes PSO or its variants, including the update of particles’ position and velocity. For the master swarm, the particles enhance themselves based on the social knowledge of master swarm and that of slave swarms. At periodic stage in the evolution, the master swarm and the whole slave swarms are forced to mix, and points are then reassigned to several sub-swarms to ensure the share of information. The process is repeated until a user-defined stopping criterion is reached. The tests of numerical simulation and the case study on hydrological model show that MSSE-PSO remarkably improves the accuracy of calibration, reduces the time of computation and enhances the performance of stability. Therefore, it is an effective and efficient global optimization method. [Copyright &y& Elsevier]

Abstract: This paper presents partitioning fuzzy K-means clustering models for interval-valued data based on suitable adaptive quadratic distances. These models furnish a fuzzy partition and a prototype for each cluster by optimizing an adequacy criterion that measures the fit between the fuzzy clusters and their representatives. These adaptive quadratic distances change at each algorithm iteration and can be either the same for all clusters or different from one cluster to another. Moreover, additional interpretation tools for individual fuzzy clusters of interval-valued data, suitable to these fuzzy clustering models, are also presented. Experiments with some interval-valued data sets demonstrate the usefulness of these fuzzy clustering models and the merit of the individual fuzzy cluster interpretation tools. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, -pencil lattices on simplicial partitions in , which are not simply connected, are studied. It is shown, how the fact that a partition is not simply connected can be used to increase the flexibility of a lattice. A local modification algorithm is developed also to deal with slight partition topology changes that may appear afterwards a lattice has already been constructed. [Copyright &y& Elsevier]

Abstract: Given a graph , a set of vertices of , and natural numbers such that , the -partition problem is to find a partition of the vertex set such that , , and induces a connected subgraph of for each . For the tripartition problem on a triconnected graph, a naive algorithm can be designed based on a directional embedding of in the two-dimensional Euclidean space. However, for graphs of large number of vertices, the implementing of this algorithm requires high precision real arithmetic to distinguish two close vertices in the plane. In this paper, we propose an algorithm for dealing with the tripartition problem by introducing a new data structure called the region graph, which represents a kind of combinatorial embedding of the given graph in the plane. The algorithm constructs a desired tripartition combinatorially in the sense that it does not require any geometrical computation with actual coordinates in the Euclidean space. [ABSTRACT FROM AUTHOR]

Abstract: Assessing the quality of ontologies is important to reuse/integrate ontologies. In this paper, we propose an approach to revise ontology inconsistency by measuring the relevant ontology constructs such as semantic partitions, axiom fanouts per concept, minimal incoherence-preserving subsets, incoherence impact value per axiom and preferable revision weight per concept in the ontology being measured. We also propose several algorithms to compute the measurement values of these ontology constructs, which can be used to pinpoint and rank which axioms and concepts are most likely to cause the ontology inconsistency. Our approach can help determine which concepts should be preferentially modified and therefore enables automatic revision of ontology inconsistency in the context of a dynamic and evolving environment. [Copyright &y& Elsevier]

Abstract: A graph is polar if the vertex set can be partitioned into and in such a way that induces a complete multipartite graph and induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite graphs, cobipartite graphs and split graphs. Recognizing polar graphs is an NP-complete problem in general, and thus it is of interest to restrict the problem to special classes of graphs. Cographs and chordal graphs are among those whose polarity can be recognized in polynomial time. The line-graphs of bipartite graphs are another class of graphs whose polarity has been characterized recently in terms of forbidden subgraphs, but no polynomial time algorithm is given. In this paper, we present an algorithm which decides whether the line-graph of an input bipartite graph is polar and constructs a polar partition when one exists. [ABSTRACT FROM AUTHOR]

Abstract: In many applied sciences the problem of revealing the underlying (crisp or fuzzy) structure (partitions or covers) in a collection of objects to be represented in non-temporal situations, measures, observations, phenomena, etc., is an essential task. Motivated by the independent use of some different partitions criteria and the theoretical and empirical analysis of some of its properties, in this paper, we introduce an incremental nested partition method which combines these partitions criteria for finding the inner structure of static and dynamic datasets. For this, we proved that there are relationships of nesting between partitions obtained, respectively, from these partition criteria, and besides that the sensitivity when a new object arrives to the dataset is rigorously studied. Our algorithm exploits all of these mathematical properties for obtaining the hierarchy of clusterings. Moreover, we realize a theoretical and experimental comparative study of our method with classical hierarchical clustering methods such as single-link and complete-link and other more recently introduced methods. The experimental results over databases of UCI repository and the AFP and TDT2 news collections show the usefulness and capability of our method to reveal different levels of information hidden in datasets. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the augmentation problem of an undirected graph with partitions of its vertices. The main issue is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, while maintaining the original partition constraint. To solve the problem, we propose a simple linear-time algorithm. To the best of our knowledge, the most efficient sequential algorithm runs in time. However, we show that it can also run in parallel time on an EREW PRAM using a linear number of processors, where is the number of vertices in the input graph. If a simple graph exists, our main algorithm ensures that it is as simple as possible. [Copyright &y& Elsevier]