OpenRaiser/Intern-Atlas huggingface dataset:
Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships
Venue: arXiv cs.SI 2012
Year: 2012

Influence diffusion and influence maximization in large-scale online social networks (OSNs) have been extensively studied, because of their impacts on enabling effective online viral marketing. Existing studies focus on social networks with only friendship relations, whereas the foe or enemy relations that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely ignored. In this paper, we make the first attempt to investigate the influence diffusion and influence maximization in OSNs with both friend and foe relations, which are modeled using positive and negative edges on signed networks. In particular, we extend the classic voter model to signed networks and analyze the dynamics of influence diffusion of two opposite opinions. We first provide systematic characterization of both short-term and long-term dynamics of influence diffusion in this model, and illustrate that the steady state behaviors of the dynamics depend on three types of graph structures, which we refer to as balanced graphs, anti-balanced graphs, and strictly unbalanced graphs. We then apply our results to solve the influence maximization problem and develop efficient algorithms to select initial seeds of one opinion that maximize either its short-term influence coverage or long-term steady state influence coverage. Extensive simulation results on both synthetic and real-world networks, such as Epinions and Slashdot, confirm our theoretical analysis on influence diffusion dynamics, and demonstrate the efficacy of our influence maximization algorithm over other heuristic algorithms.
Comparative study of Financial Time Series Prediction by Artificial Neural Network with Gradient Descent Learning
Venue: arXiv cs.NE 2012
Year: 2012

Financial forecasting is an example of a signal processing problem which is challenging due to Small sample sizes, high noise, non-stationarity, and non-linearity,but fast forecasting of stock market price is very important for strategic business planning.Present study is aimed to develop a comparative predictive model with Feedforward Multilayer Artificial Neural Network & Recurrent Time Delay Neural Network for the Financial Timeseries Prediction.This study is developed with the help of historical stockprice dataset made available by GoogleFinance.To develop this prediction model Backpropagation method with Gradient Descent learning has been implemented.Finally the Neural Net, learned with said algorithm is found to be skillful predictor for non-stationary noisy Financial Timeseries.
Decentralised LTL Monitoring
Venue: arXiv cs.SE 2012
Year: 2012

Users wanting to monitor distributed or component-based systems often perceive them as monolithic systems which, seen from the outside, exhibit a uniform behaviour as opposed to many components displaying many local behaviours that together constitute the system's global behaviour. This level of abstraction is often reasonable, hiding implementation details from users who may want to specify the system's global behaviour in terms of an LTL formula. However, the problem that arises then is how such a specification can actually be monitored in a distributed system that has no central data collection point, where all the components' local behaviours are observable. In this case, the LTL specification needs to be decomposed into sub-formulae which, in turn, need to be distributed amongst the components' locally attached monitors, each of which sees only a distinct part of the global behaviour. The main contribution of this paper is an algorithm for distributing and monitoring LTL formulae, such that satisfac- tion or violation of specifications can be detected by local monitors alone. We present an implementation and show that our algorithm introduces only a minimum delay in detecting satisfaction/violation of a specification. Moreover, our practical results show that the communication overhead introduced by the local monitors is considerably lower than the number of messages that would need to be sent to a central data collection point.
Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis
Venue: arXiv cs.LO 2012
Year: 2012

We introduce a new domain for finding precise numerical invariants of programs by abstract interpretation. This domain, which consists of level sets of non-linear functions, generalizes the domain of linear "templates" introduced by Manna, Sankaranarayanan, and Sipma. In the case of quadratic templates, we use Shor's semi-definite relaxation to derive computable yet precise abstractions of semantic functionals, and we show that the abstract fixpoint equation can be solved accurately by coupling policy iteration and semi-definite programming. We demonstrate the interest of our approach on a series of examples (filters, integration schemes) including a degenerate one (symplectic scheme).
Greediness and Equilibrium in Congestion Games
Venue: arXiv cs.GT 2012
Year: 2012

Rosenthal (1973) introduced the class of congestion games and proved that they always possess a Nash equilibrium in pure strategies. Fotakis et al. (2005) introduce the notion of a greedy strategy tuple, where players sequentially and irrevocably choose a strategy that is a best response to the choice of strategies by former players. Whereas the former solution concept is driven by strong assumptions on the rationality of the players and the common knowledge thereof, the latter assumes very little rationality on the players' behavior. From Fotakis \cite{fotakis10} it follows that for Tree Representable congestion Games greedy behavior leads to a NE. In this paper we obtain necessary and sufficient conditions for the equivalence of these two solution concepts. Such equivalence enhances the viability of these concepts as realistic outcomes of the environment. The conditions for such equivalence to emerge for monotone symmetric games is that the strategy set has a tree-form, or equivalently is a `extension-parallel graph'.
Nested Inequalities Among Divergence Measures
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we have considered a single inequality having 11 known divergence measures. This inequality include measures like: Jeffryes-Kullback-Leiber J-divergence, Jensen-Shannon divergence (Burbea-Rao, 1982), arithmetic-geometric mean divergence (Taneja, 1995), Hellinger discrimination, symmetric chi-square divergence, triangular discrimination, etc. All these measures are well-known in the literature on Information theory and Statistics. This sequence of 11 measures also include measures due to Kumar and Johnson (2005) and Jain and Srivastava (2007). Three measures arising due to some mean divergences also appears in this inequality. Based on non-negative differences arising due to this single inequality of 11 measures, we have put more than 40 divergence measures in nested or sequential form. Idea of reverse inequalities is also introduced.
Publish-Subscribe Systems via Gossip: a Study based on Complex Networks
Venue: arXiv cs.DC 2012
Year: 2012

This paper analyzes the adoption of unstructured P2P overlay networks to build publish-subscribe systems. We consider a very simple distributed communication protocol, based on gossip and on the local knowledge each node has about subscriptions made by its neighbours. In particular, upon reception (or generation) of a novel event, a node sends it to those neighbours whose subscriptions match that event. Moreover, the node gossips the event to its "non-interested" neighbours, so that the event can be spread through the overlay. A mathematical analysis is provided to estimate the number of nodes receiving the event, based on the network topology, the amount of subscribers and the gossip probability. These outcomes are compared to those obtained via simulation. Results show even when the amount of subscribers represents a very small (yet non-negligible) portion of network nodes, by tuning the gossip probability the event can percolate through the overlay. Hence, the use of unstructured networks. coupled with simple dissemination protocols, represents a viable approach to build peer-to-peer publish-subscribe applications.
Simple and Effective Dynamic Provisioning for Power-Proportional Data Centers
Venue: arXiv cs.PF 2012
Year: 2012

Energy consumption represents a significant cost in data center operation. A large fraction of the energy, however, is used to power idle servers when the workload is low. Dynamic provisioning techniques aim at saving this portion of the energy, by turning off unnecessary servers. In this paper, we explore how much performance gain can knowing future workload information brings to dynamic provisioning. In particular, we study the dynamic provisioning problem under the cost model that a running server consumes a fixed amount energy per unit time, and develop online solutions with and without future workload information available. We first reveal an elegant structure of the off-line dynamic provisioning problem, which allows us to characterize and achieve the optimal solution in a {}"divide-and-conquer" manner. We then exploit this insight to design three online algorithms with competitive ratios $2-α$, $(e-α)/(e-1)\approx1.58-α/(e-1)$ and $e/(e-1+α)$, respectively, where $0\leqα\leq1$ is the fraction of a critical window in which future workload information is available. A fundamental observation is that \emph{future workload information beyond the critical window will not} \emph{improve dynamic provisioning performance}. Our algorithms are decentralized and are simple to implement. We demonstrate their effectiveness in simulations using real-world traces. We also compare their performance with state-of-the-art solutions.
Reaching an Optimal Consensus: Dynamical Systems that Compute Intersections of Convex Sets
Venue: arXiv cs.MA 2012
Year: 2012

In this paper, multi-agent systems minimizing a sum of objective functions, where each component is only known to a particular node, is considered for continuous-time dynamics with time-varying interconnection topologies. Assuming that each node can observe a convex solution set of its optimization component, and the intersection of all such sets is nonempty, the considered optimization problem is converted to an intersection computation problem. By a simple distributed control rule, the considered multi-agent system with continuous-time dynamics achieves not only a consensus, but also an optimal agreement within the optimal solution set of the overall optimization objective. Directed and bidirectional communications are studied, respectively, and connectivity conditions are given to ensure a global optimal consensus. In this way, the corresponding intersection computation problem is solved by the proposed decentralized continuous-time algorithm. We establish several important properties of the distance functions with respect to the global optimal solution set and a class of invariant sets with the help of convex and non-smooth analysis.
Jungles, bundles, and fixed parameter tractability
Venue: arXiv cs.DS 2012
Year: 2012

We give a fixed-parameter tractable (FPT) approximation algorithm computing the path-width of a tournament, and more generally, of a semi-complete digraph. Based on this result, we prove that topological containment and rooted immersion problems are FPT on semi-complete digraphs.
Active Learning of Halfspaces under a Margin Assumption
Venue: arXiv cs.LG 2012
Year: 2012

We derive and analyze a new, efficient, pool-based active learning algorithm for halfspaces, called ALuMA. Most previous algorithms show exponential improvement in the label complexity assuming that the distribution over the instance space is close to uniform. This assumption rarely holds in practical applications. Instead, we study the label complexity under a large-margin assumption -- a much more realistic condition, as evident by the success of margin-based algorithms such as SVM. Our algorithm is computationally efficient and comes with formal guarantees on its label complexity. It also naturally extends to the non-separable case and to non-linear kernels. Experiments illustrate the clear advantage of ALuMA over other active learning algorithms.
Wireless Network-Coded Three-Way Relaying Using Latin Cubes
Venue: arXiv cs.IT 2012
Year: 2012

The design of modulation schemes for the physical layer network-coded three-way wireless relaying scenario is considered. The protocol employs two phases: Multiple Access (MA) phase and Broadcast (BC) phase with each phase utilizing one channel use. For the two-way relaying scenario, it was observed by Koike-Akino et al. \cite{KPT}, that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase and all these network coding maps should satisfy a requirement called \textit{exclusive law}. This paper does the equivalent for the three-way relaying scenario. We show that when the three users transmit points from the same 4-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a Latin Cube of Second Order. The network code map used by the relay for the BC phase is explicitly obtained and is aimed at reducing the effect of interference at the MA stage.
Heegard-Berger and Cascade Source Coding Problems with Common Reconstruction Constraints
Venue: arXiv cs.IT 2012
Year: 2012

For the HB problem with the CR constraint, the rate-distortion function is derived under the assumption that the side information sequences are (stochastically) degraded. The rate-distortion function is also calculated explicitly for three examples, namely Gaussian source and side information with quadratic distortion metric, and binary source and side information with erasure and Hamming distortion metrics. The rate-distortion function is then characterized for the HB problem with cooperating decoders and (physically) degraded side information. For the cascade problem with the CR constraint, the rate-distortion region is obtained under the assumption that side information at the final node is physically degraded with respect to that at the intermediate node. For the latter two cases, it is worth emphasizing that the corresponding problem without the CR constraint is still open. Outer and inner bounds on the rate-distortion region are also obtained for the cascade problem under the assumption that the side information at the intermediate node is physically degraded with respect to that at the final node. For the three examples mentioned above, the bounds are shown to coincide. Finally, for the HB problem, the rate-distortion function is obtained under the more general requirement of constrained reconstruction, whereby the decoder's estimate must be recovered at the encoder only within some distortion.
Distributed Priority Synthesis and its Applications
Venue: arXiv cs.LO 2012
Year: 2012

Given a set of interacting components with non-deterministic variable update and given safety requirements, the goal of priority synthesis is to restrict, by means of priorities, the set of possible interactions in such a way as to guarantee the given safety conditions for all possible runs. In distributed priority synthesis we are interested in obtaining local sets of priorities, which are deployed in terms of local component controllers sharing intended next moves between components in local neighborhoods only. These possible communication paths between local controllers are specified by means of a communication architecture. We formally define the problem of distributed priority synthesis in terms of a multi-player safety game between players for (angelically) selecting the next transition of the components and an environment for (demonically) updating uncontrollable variables; this problem is NP-complete. We propose several optimizations including a solution-space exploration based on a diagnosis method using a nested extension of the usual attractor computation in games together with a reduction to corresponding SAT problems. When diagnosis fails, the method proposes potential candidates to guide the exploration. These optimized algorithms for solving distributed priority synthesis problems have been integrated into our VissBIP framework. An experimental validation of this implementation is performed using a range of case studies including scheduling in multicore processors and modular robotics.
Approximation Algorithms for Edge Partitioned Vertex Cover Problems
Venue: arXiv cs.DS 2012
Year: 2012

We consider a natural generalization of the Partial Vertex Cover problem. Here an instance consists of a graph G = (V,E), a positive cost function c: V-> Z^{+}, a partition $P_1,..., P_r$ of the edge set $E$, and a parameter $k_i$ for each partition $P_i$. The goal is to find a minimum cost set of vertices which cover at least $k_i$ edges from the partition $P_i$. We call this the Partition Vertex Cover problem. In this paper, we give matching upper and lower bound on the approximability of this problem. Our algorithm is based on a novel LP relaxation for this problem. This LP relaxation is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. We show that this LP has integrality gap of $O(log r)$, where $r$ is the number of sets in the partition of the edge set. We also extend our result to more general settings.
Perfectly secure encryption of individual sequences
Venue: arXiv cs.IT 2012
Year: 2012

In analogy to the well-known notion of finite--state compressibility of individual sequences, due to Lempel and Ziv, we define a similar notion of "finite-state encryptability" of an individual plaintext sequence, as the minimum asymptotic key rate that must be consumed by finite-state encrypters so as to guarantee perfect secrecy in a well-defined sense. Our main basic result is that the finite-state encryptability is equal to the finite-state compressibility for every individual sequence. This is in parallelism to Shannon's classical probabilistic counterpart result, asserting that the minimum required key rate is equal to the entropy rate of the source. However, the redundancy, defined as the gap between the upper bound (direct part) and the lower bound (converse part) in the encryption problem, turns out to decay at a different rate (in fact, much slower) than the analogous redundancy associated with the compression problem. We also extend our main theorem in several directions, allowing: (i) availability of side information (SI) at the encrypter/decrypter/eavesdropper, (ii) lossy reconstruction at the decrypter, and (iii) the combination of both lossy reconstruction and SI, in the spirit of the Wyner--Ziv problem.
Threshold Choice Methods: the Missing Link
Venue: arXiv cs.AI 2012
Year: 2012

Many performance metrics have been introduced for the evaluation of classification performance, with different origins and niches of application: accuracy, macro-accuracy, area under the ROC curve, the ROC convex hull, the absolute error, and the Brier score (with its decomposition into refinement and calibration). One way of understanding the relation among some of these metrics is the use of variable operating conditions (either in the form of misclassification costs or class proportions). Thus, a metric may correspond to some expected loss over a range of operating conditions. One dimension for the analysis has been precisely the distribution we take for this range of operating conditions, leading to some important connections in the area of proper scoring rules. However, we show that there is another dimension which has not received attention in the analysis of performance metrics. This new dimension is given by the decision rule, which is typically implemented as a threshold choice method when using scoring models. In this paper, we explore many old and new threshold choice methods: fixed, score-uniform, score-driven, rate-driven and optimal, among others. By calculating the loss of these methods for a uniform range of operating conditions we get the 0-1 loss, the absolute error, the Brier score (mean squared error), the AUC and the refinement loss respectively. This provides a comprehensive view of performance metrics as well as a systematic approach to loss minimisation, namely: take a model, apply several threshold choice methods consistent with the information which is (and will be) available about the operating condition, and compare their expected losses. In order to assist in this procedure we also derive several connections between the aforementioned performance metrics, and we highlight the role of calibration in choosing the threshold choice method.
On the Treewidth of Dynamic Graphs
Venue: arXiv cs.CC 2012
Year: 2012

Dynamic graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modelling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability. In this paper we are concerned with the treewidth of dynamic graphs. We focus on metatheorems, which allow the generation of a series of results based on general properties of classes of structures. In graph theory two major metatheorems on treewidth provide complexity classifications by employing structural graph measures and finite model theory. Courcelle's Theorem gives a general tractability result for problems expressible in monadic second order logic on graphs of bounded treewidth, and Frick & Grohe demonstrate a similar result for first order logic and graphs of bounded local treewidth. We extend these theorems by showing that dynamic graphs of bounded (local) treewidth where the length of time over which the graph evolves and is observed is finite and bounded can be modelled in such a way that the (local) treewidth of the underlying graph is maintained. We show the application of these results to problems in dynamic graph theory and dynamic extensions to static problems. In addition we demonstrate that certain widely used dynamic graph classes naturally have bounded local treewidth.
Design and Implementation of a Simple Web Search Engine
Venue: arXiv cs.IR 2012
Year: 2012

We present a simple web search engine for indexing and searching html documents using python programming language. Because python is well known for its simple syntax and strong support for main operating systems, we hope it will be beneficial for learning information retrieval techniques, especially web search engine technology.
Higher-Order Momentum Distributions and Locally Affine LDDMM Registration
Venue: arXiv cs.CV 2012
Year: 2012

To achieve sparse parametrizations that allows intuitive analysis, we aim to represent deformation with a basis containing interpretable elements, and we wish to use elements that have the description capacity to represent the deformation compactly. To accomplish this, we introduce in this paper higher-order momentum distributions in the LDDMM registration framework. While the zeroth order moments previously used in LDDMM only describe local displacement, the first-order momenta that are proposed here represent a basis that allows local description of affine transformations and subsequent compact description of non-translational movement in a globally non-rigid deformation. The resulting representation contains directly interpretable information from both mathematical and modeling perspectives. We develop the mathematical construction of the registration framework with higher-order momenta, we show the implications for sparse image registration and deformation description, and we provide examples of how the parametrization enables registration with a very low number of parameters. The capacity and interpretability of the parametrization using higher-order momenta lead to natural modeling of articulated movement, and the method promises to be useful for quantifying ventricle expansion and progressing atrophy during Alzheimer's disease.