To find interesting structure in networks, community detection algorithms have to take into account not only the network topology, but also dynamics of interactions between nodes. We investigate this claim using the paradigm of synchronization in a network of coupled oscillators. As the network evolves to a global steady state, nodes belonging to the same community synchronize faster than nodes belonging to different communities. Traditionally, nodes in network synchronization models are coupled via one-to-one, or conservative interactions. However, social interactions are often one-to-many, as for example, in social media, where users broadcast messages to all their followers. We formulate a novel model of synchronization in a network of coupled oscillators in which the oscillators are coupled via one-to-many, or non-conservative interactions. We study the dynamics of different interaction models and contrast their spectral properties. To find multi-scale community structure in a network of interacting nodes, we define a similarity function that measures the degree to which nodes are synchronized and use it to hierarchically cluster nodes. We study real-world social networks, including networks of two social media providers. To evaluate the quality of the discovered communities in a social media network we propose a community quality metric based on user activity. We find that conservative and non-conservative interaction models lead to dramatically different views of community structure even within the same network. Our work offers a novel mathematical framework for exploring the relationship between network structure, topology and dynamics.
It can be shown that some of the interaction models described above not only solve certain regularized Semi-Definite Programs but also give fast solutions to these problems @cite_12 .
@cite_12
2672830324 2615873886 1967311985 1971332773 2463117017 2963760054 2136907259 1994320209 2046945713 1629950647 1516535258 2146807782 2082585576 2706788079 2123429492 2098579316 2079632486 2100241850 1540263588 2962764388
The notions of serializability, linearizability, and sequential consistency are used in the specification of concurrent systems. We show that the model checking problem for each of these properties can be cast in terms of the containment of one regular language in another regular language shuffled using a semicommutative alphabet. The three model checking problems are shown to be, respectively, in Pspace, in Expspace, and undecidable. Recent breakthroughs have been made in the use of semi-definite programming and its application to real polynomial solving. For example, the real radical of a zero dimensional ideal, can be determined by such approaches. Some progress has been made on the determination of the real radical in positive dimension by Ma, Wang and Zhi[5, 4]. Such work involves the determination of maximal rank semidefinite matrices. Existing methods are computationally expensive and have poorer accuracy on larger examples. In previous work we showed that regularity in the form of the Slater constraint qualification (strict feasibility) fails for the moment matrix in the SDP feasibility problem[6]. We used facial reduction to obtain a smaller regularized problem for which strict feasibility holds. However we did not have a theoretical guarantee that our methods, based on facial reduction and Douglas-Rachford iteration ensured the satisfaction of the maximum rank condition. Our work is motivated by the problems above. We discuss how to compute the moment matrix and its kernel using facial reduction techniques where the maximum rank property can be guaranteed by solving the dual problem. The facial reduction algorithms on the primal form is presented. We give examples that exhibit for the first time additional facial reductions beyond the first which are effective in practice with much better accuracy than SeDuMi(CVX). In this paper we study linear-programming based approaches to the maximum matching problem in the semi-streaming model. In this model edges are presented sequentially, possibly in an adversarial order, and we are only allowed to use a small space. The allowed space is near linear in the number of vertices (and sublinear in the number of edges) of the input graph. The semi-streaming model is relevant in the context of processing of very large graphs. In recent years, there have been several new and exciting results in the semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. In this paper we present several techniques to adapt and optimize linear-programming based approaches in the semi-streaming model. We use the maximum matching problem as a foil to demonstrate the effectiveness of adapting such tools in this model. As a consequence we improve almost all previous results on the semi-streaming maximum matching problem. We also prove new results on interesting variants. We address the verification problem of finite-state concurrent programs running under weak memory models. These models capture the reordering of program (read and write) operations done by modern multi-processor architectures for performance. The verification problem we study is crucial for the correctness of concurrency libraries and other performance-critical system services employing lock-free synchronization, as well as for the correctness of compiler backends that generate code targeted to run on such architectures. We consider in this paper combinations of three well-known program order relaxations. We consider first the "write to read" relaxation, which corresponds to the TSO (Total Store Ordering) model. This relaxation is used in most hardware architectures available today. Then, we consider models obtained by adding either (1) the "write to write" relaxation, leading to a model which is essentially PSO (Partial Store Ordering), or (2) the "read to read write" relaxation, or (3) both of them, as it is done in the RMO (Relaxed Memory Ordering) model for instance. We define abstract operational models for these weak memory models based on state machines with (potentially unbounded) FIFO buffers, and we investigate the decidability of their reachability and their repeated reachability problems. We prove that the reachability problem is decidable for the TSO model, as well as for its extension with "write to write" relaxation (PSO). Furthermore, we prove that the reachability problem becomes undecidable when the "read to read write" relaxation is added to either of these two memory models, and we give a condition under which this addition preserves the decidability of the reachability problem. We show also that the repeated reachability problem is undecidable for all the considered memory models. Approximations of solutions of fractional Laplacian equations on bounded domains are considered. Such equations allow global interactions between points separated by arbitrarily large distances. Two approximations are introduced. First, interactions are localized so that only points less than some specified distance, referred to as the interaction radius, are allowed to interact. The resulting truncated problem is a special case of a more general nonlocal diffusion problem. The second approximation is the spatial discretization of the related nonlocal diffusion problem. A recently developed abstract framework for asymptotically compatible schemes is applied to prove convergence results for solutions of the truncated and discretized problem to the solutions of the fractional Laplacian problems. Intermediate results also provide new convergence results for the nonlocal diffusion problem. Special attention is paid to limiting behaviors as the interaction radius increases and the spatial grid size decreases, regardless of how these parameters may or may not be dependent. In particular, we show that conforming Galerkin finite element approximations of the nonlocal diffusion equation are always asymptotically compatible schemes for the corresponding fractional Laplacian model as the interaction radius increases and the grid size decreases. The results are developed with minimal regularity assumptions on the solution and are applicable to general domains and general geometric meshes with no restriction on the space dimension and with data that are only required to be square integrable. Furthermore, our results also solve an open conjecture given in the literature about the convergence of numerical solutions on a fixed mesh as the interaction radius increases. We consider the Widom–Rowlinson model of two types of interacting particles on d -regular graphs. We prove a tight upper bound on the occupancy fraction, the expected fraction of vertices occupied by a particle under a random configuration from the model. The upper bound is achieved uniquely by unions of complete graphs on d + 1 vertices, K d +1 . As a corollary we find that K d +1 also maximizes the normalized partition function of the Widom–Rowlinson model over the class of d -regular graphs. A special case of this shows that the normalized number of homomorphisms from any d -regular graph G to the graph H WR , a path on three vertices with a loop on each vertex, is maximized by K d +1 . This proves a conjecture of Galvin. We consider the problem of maximizing the algebraic connectivity of the communication graph in a network of mobile robots by moving them into appropriate positions. We describe the Laplacian of the graph as dependent on the pairwise distance between the robots and formulate an approximate problem as a Semi-Definite Program (SDP). We propose a consistent, non-iterative distributed solution by solving local SDP's which use information only from nearby neighboring robots. Numerical simulations show the performance of the algorithm with respect to the centralized solution. The well-known least squares semidefinite programming (LSSDP) problem seeks the nearest adjustment of a given symmetric matrix in the intersection of the cone of positive semidefinite matrices and a set of linear constraints, and it captures many applications in diversing fields. The task of solving large-scale LSSDP with many linear constraints, however, is numerically challenging. This paper mainly shows the applicability of the classical alternating direction method (ADM) for solving LSSDP and convinces the efficiency of the ADM approach. We compare the ADM approach with some other existing approaches numerically, and we show the superiority of ADM for solving large-scale LSSDP. Standard generalized additive models (GAMs) usually model the dependent variable as a sum of univariate models. Although previous studies have shown that standard GAMs can be interpreted by users, their accuracy is significantly less than more complex models that permit interactions. In this paper, we suggest adding selected terms of interacting pairs of features to standard GAMs. The resulting models, which we call GA2 M $-models, for Generalized Additive Models plus Interactions, consist of univariate terms and a small number of pairwise interaction terms. Since these models only include one- and two-dimensional components, the components of GA2M-models can be visualized and interpreted by users. To explore the huge (quadratic) number of pairs of features, we develop a novel, computationally efficient method called FAST for ranking all possible pairs of features as candidates for inclusion into the model. In a large-scale empirical study, we show the effectiveness of FAST in ranking candidate pairs of features. In addition, we show the surprising result that GA2M-models have almost the same performance as the best full-complexity models on a number of real datasets. Thus this paper postulates that for many problems, GA2M-models can yield models that are both intelligible and accurate. In this paper, we study the non-bipartite maximum matching problem in the semi-streaming model. The maximum matching problem in the semi-streaming model has received a significant amount of attention lately. While the problem has been somewhat well solved for bipartite graphs, the known algorithms for non-bipartite graphs use @math passes or @math time to compute a @math approximation. In this paper we provide the first FPTAS (polynomial in @math ) for the problem which is efficient in both the running time and the number of passes. We also show that we can estimate the size of the matching in @math passes using slightly superlinear space. To achieve both results, we use the structural properties of the matching polytope such as the laminarity of the tight sets and total dual integrality. The algorithms are iterative, and are based on the fractional packing and covering framework. However the formulations herein require exponentially many variables or constraints. We use laminarity, metric embeddings and graph sparsification to reduce the space required by the algorithms in between and across the iterations. This is the first use of these ideas in the semi-streaming model to solve a combinatorial optimization problem. Partial stable models for deductive databases, i.e., normal function-free logic programs (also called datalog programs), have two equivalent definitions: one based on 3-valued logics and another based on the notion of unfounded set. The notion of partial stable model has been extended to disjunctive deductive databases using 3-valued logics. In this paper, a characterization of partial stable models for disjunctive datalog programs is given using a suitable extension of the notion of unfounded set. Two interesting sub-classes of partial stable models, M-stable (Maximal-stable) (also called regular models, preferred extension,and maximal stable classes) and L-stable (Least undefined-stable) models, are then extended from normal to disjunctive datalog programs. On the one hand, L-stable models are shown to be the natural relaxation of the notion of total stable model; on the other hand the less strict M-stable models, endowed with a nice modularity property, may be appealing from the programming and computational point of view. M-stable and L-stable models are also compared with the regular models for disjunctive datalog programs recently proposed in the literature. Even years ago, published an influential study on energy minimization methods for Markov random fields (MRF). This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenominal success of random field models means that the kinds of inference problems we solve have changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large label-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of 24 state-of-art techniques on a corpus of 2,300 energy minimization instances from 20 diverse computer vision applications. To ensure reproducibility, we evaluate all methods in the OpenGM2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types. In this paper, we study the safe navigation of a mobile robot through crowds of dynamic agents with uncertain trajectories. Existing algorithms suffer from the “freezing robot” problem: once the environment surpasses a certain level of complexity, the planner decides that all forward paths are unsafe, and the robot freezes in place (or performs unnecessary maneuvers) to avoid collisions. Since a feasible path typically exists, this behavior is suboptimal. Existing approaches have focused on reducing the predictive uncertainty for individual agents by employing more informed models or heuristically limiting the predictive covariance to prevent this overcautious behavior. In this work, we demonstrate that both the individual prediction and the predictive uncertainty have little to do with the frozen robot problem. Our key insight is that dynamic agents solve the frozen robot problem by engaging in “joint collision avoidance”: They cooperatively make room to create feasible trajectories. We develop IGP, a nonparametric statistical model based on dependent output Gaussian processes that can estimate crowd interaction from data. Our model naturally captures the non-Markov nature of agent trajectories, as well as their goal-driven navigation. We then show how planning in this model can be efficiently implemented using particle based inference. Lastly, we evaluate our model on a dataset of pedestrians entering and leaving a building, first comparing the model with actual pedestrians, and find that the algorithm either outperforms human pedestrians or performs very similarly to the pedestrians. We also present an experiment where a covariance reduction method results in highly overcautious behavior, while our model performs desirably. The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size are defined. With a fairness condition on interactions, the concept of stable computation of a function or predicate is defined. Protocols are given that stably compute any predicate in the class definable by formulas of Presburger arithmetic, which includes Boolean combinations of threshold-k, majority, and equivalence modulo m. All stably computable predicates are shown to be in NL. Assuming uniform random sampling of interacting pairs yields the model of conjugating automata. Any counter machine with O (1) counters of capacity O (n) can be simulated with high probability by a conjugating automaton in a population of size n. All predicates computable with high probability in this model are shown to be in P; they can also be computed by a randomized logspace machine in exponential time. Several open problems and promising future directions are discussed. We consider the model of population protocols introduced by (Computation in networks of passively mobile finite-state sensors, pp. 290–299. ACM, New York, 2004), in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the family of all-pairs communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates. We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P ∩ RL. Several open problems and promising future directions are discussed. The property of locality in program behavior has been studied and modelled extensively because of its application to memory design, code optimization, multiprogramming etc. We propose a k order Markov chain based scheme to model the sequence of time intervals between successive references to the same address in memory during program execution. Each unique address in a program is modelled separately. To validate our model, which we call the Inter-Reference Gap (IRG) model, we show substantial improvements in three different areas where it is applied. (1) We improve upon the miss ratio for the Least Recently Used (LRU) memory replacement algorithm by up to 37 . (2) We achieve up to 22 space-time product improvement over the Working Set (WS) algorithm for dynamic memory management. (3) A new trace compression technique is proposed which compresses up to 2.5 with zero error in WS simulations and up to 3.7 error in the LRU simulations. All these results are obtained experimentally, via trace driven simulations over a wide range of cache traces, page reference traces, object traces and database traces. We consider the problem of Bayesian inference of graphical structure describing the interactions among multiple vector time-series. A directed temporal interaction model is presented which assumes a fixed dependence structure among time-series. Using a conjugate prior over this model’s structure and parameters, we focus our attention on characterizing the exact posterior uncertainty in the structure given data. The model is extended via the introduction of a dynamically evolving latent variable which indexes dependence structures over time. Performing inference using this model yields promising results when analyzing the interaction of multiple tracked moving objects. We investigate a generalization of weight-constraint programs with stable semantics, as implemented in the ASP solver smodels. Our programs admit atoms of the form ( X, F ) where X is a finite set of propositional atoms and ( F ) is an arbitrary family of subsets of X. We call such atoms set constaints and show that the concept of stable model can be generalized to programs admitting set constraints both in the bodies and the heads of clauses. Natural tools to investigate the fixpoint semantics for such programs are nondeterministic operators in complete lattices. We prove two fixpoint theorems for such operators. Many problems in control theory can be formulated as semidefinite programs (SDPs). For large-scale SDPs, it is important to exploit the inherent sparsity to improve scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). We show that chordal decomposition can be applied to either the primal or the dual standard form of a sparse SDP, resulting in scaled versions of ADMM algorithms with the same computational cost. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, followed by a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in CDCS, an open source add-on to MATLAB. Numerical experiments on large-scale sparse problems in SDPLIB and random SDPs with block-arrow sparse patterns show speedups compared to some common state-of-the-art software packages.