OpenRaiser/Intern-Atlas huggingface dataset:
Overlapping Community Detection in Networks: the State of the Art and Comparative Study
Venue: arXiv cs.SI 2012
Year: 2012

This paper reviews the state of the art in overlapping community detection algorithms, quality measures, and benchmarks. A thorough comparison of different algorithms (a total of fourteen) is provided. In addition to community level evaluation, we propose a framework for evaluating algorithms' ability to detect overlapping nodes, which helps to assess over-detection and under-detection. After considering community level detection performance measured by Normalized Mutual Information, the Omega index, and node level detection performance measured by F-score, we reached the following conclusions. For low overlapping density networks, SLPA, OSLOM, Game and COPRA offer better performance than the other tested algorithms. For networks with high overlapping density and high overlapping diversity, both SLPA and Game provide relatively stable performance. However, test results also suggest that the detection in such networks is still not yet fully resolved. A common feature observed by various algorithms in real-world networks is the relatively small fraction of overlapping nodes (typically less than 30%), each of which belongs to only 2 or 3 communities.
Geometric Graph Properties of the Spatial Preferred Attachment model
Venue: arXiv cs.SI 2012
Year: 2012

The spatial preferred attachment (SPA) model is a model for networked information spaces such as domains of the World Wide Web, citation graphs, and on-line social networks. It uses a metric space to model the hidden attributes of the vertices. Thus, vertices are elements of a metric space, and link formation depends on the metric distance between vertices. We show, through theoretical analysis and simulation, that for graphs formed according to the SPA model it is possible to infer the metric distance between vertices from the link structure of the graph. Precisely, the estimate is based on the number of common neighbours of a pair of vertices, a measure known as {\sl co-citation}. To be able to calculate this estimate, we derive a precise relation between the number of common neighbours and metric distance. We also analyze the distribution of {\sl edge lengths}, where the length of an edge is the metric distance between its end points. We show that this distribution has three different regimes, and that the tail of this distribution follows a power law.
Record-replay debugging for the SCOOP concurrency model
Venue: arXiv cs.DC 2012
Year: 2012

To support developers in writing reliable and efficient concurrent programs, novel concurrent programming abstractions have been proposed in recent years. Programming with such abstractions requires new analysis tools because the execution semantics often differs considerably from established models. We present a record-replay technique for programs written in SCOOP, an object-oriented programming model for concurrency. The resulting tool enables developers to reproduce the nondeterministic execution of a concurrent program, a necessary prerequisite for debugging and testing.
Modular organisation of interaction networks based on asymptotic dynamics
Venue: arXiv cs.DM 2012
Year: 2012

This paper investigates questions related to the modularity in discrete models of biological interaction networks. We develop a theoretical framework based on the analysis of their asymptotic dynamics. More precisely, we exhibit formal conditions under which agents of interaction networks can be grouped into modules. As a main result, we show that the usual decomposition in strongly connected components fulfils the conditions of being a modular organisation. Furthermore, we point out that our framework enables a finer analysis providing a decomposition in elementary modules.
T-functions revisited: New criteria for bijectivity/transitivity
Venue: arXiv cs.CR 2012
Year: 2012

The paper presents new criteria for bijectivity/transitivity of T-functions and fast knapsack-like algorithm of evaluation of a T-function. Our approach is based on non-Archimedean ergodic theory: Both the criteria and algorithm use van der Put series to represent 1-Lipschitz $p$-adic functions and to study measure-preservation/ergodicity of these.
Information storage capacity of discrete spin systems
Venue: arXiv cs.IT 2012
Year: 2012

Understanding the limits imposed on information storage capacity of physical systems is a problem of fundamental and practical importance which bridges physics and information science. There is a well-known upper bound on the amount of information that can be stored reliably in a given volume of discrete spin systems which are supported by gapped local Hamiltonians. However, all the previously known systems were far below this theoretical bound, and it remained open whether there exists a gapped spin system that saturates this bound. Here, we present a construction of spin systems which saturate this theoretical limit asymptotically by borrowing an idea from fractal properties arising in the Sierpinski triangle. Our construction provides not only the best classical error-correcting code which is physically realizable as the energy ground space of gapped frustration-free Hamiltonians, but also a new research avenue for correlated spin phases with fractal spin configurations.
On the Measurement of Privacy as an Attacker's Estimation Error
Venue: arXiv cs.IT 2012
Year: 2012

A wide variety of privacy metrics have been proposed in the literature to evaluate the level of protection offered by privacy enhancing-technologies. Most of these metrics are specific to concrete systems and adversarial models, and are difficult to generalize or translate to other contexts. Furthermore, a better understanding of the relationships between the different privacy metrics is needed to enable more grounded and systematic approach to measuring privacy, as well as to assist systems designers in selecting the most appropriate metric for a given application. In this work we propose a theoretical framework for privacy-preserving systems, endowed with a general definition of privacy in terms of the estimation error incurred by an attacker who aims to disclose the private information that the system is designed to conceal. We show that our framework permits interpreting and comparing a number of well-known metrics under a common perspective. The arguments behind these interpretations are based on fundamental results related to the theories of information, probability and Bayes decision.
A Closed Form Expression for the Exact Bit Error Probability for Viterbi Decoding of Convolutional Codes
Venue: arXiv cs.IT 2012
Year: 2012

In 1995, Best et al. published a formula for the exact bit error probability for Viterbi decoding of the rate R=1/2, memory m=1 (2-state) convolutional encoder with generator matrix G(D)=(1 1+D) when used to communicate over the binary symmetric channel. Their formula was later extended to the rate R=1/2, memory m=2 (4-state) convolutional encoder with generator matrix G(D)=(1+D^2 1+D+D^2) by Lentmaier et al. In this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix equation yields a closed form expression for the exact bit error probability. As special cases, the expressions obtained by Best et al. for the 2-state encoder and by Lentmaier et al. for a 4-state encoder are obtained. The closed form expression derived in this paper is evaluated for various realizations of encoders, including rate R=1/2 and R=2/3 encoders, of as many as 16 states. Moreover, it is shown that it is straightforward to extend the approach to communication over the quantized additive white Gaussian noise channel.
Model-based Utility Functions
Venue: arXiv cs.AI 2012
Year: 2012

Orseau and Ring, as well as Dewey, have recently described problems, including self-delusion, with the behavior of agents using various definitions of utility functions. An agent's utility function is defined in terms of the agent's history of interactions with its environment. This paper argues, via two examples, that the behavior problems can be avoided by formulating the utility function in two steps: 1) inferring a model of the environment from interactions, and 2) computing utility as a function of the environment model. Basing a utility function on a model that the agent must learn implies that the utility function must initially be expressed in terms of specifications to be matched to structures in the learned model. These specifications constitute prior assumptions about the environment so this approach will not work with arbitrary environments. But the approach should work for agents designed by humans to act in the physical world. The paper also addresses the issue of self-modifying agents and shows that if provided with the possibility to modify their utility functions agents will not choose to do so, under some usual assumptions.
Four Degrees of Separation
Venue: arXiv cs.SI 2012
Year: 2012

Frigyes Karinthy, in his 1929 short story "Láancszemek" ("Chains") suggested that any two persons are distanced by at most six friendship links. (The exact wording of the story is slightly ambiguous: "He bet us that, using no more than five individuals, one of whom is a personal acquaintance, he could contact the selected individual [...]". It is not completely clear whether the selected individual is part of the five, so this could actually allude to distance five or six in the language of graph theory, but the "six degrees of separation" phrase stuck after John Guare's 1990 eponymous play. Following Milgram's definition and Guare's interpretation, we will assume that "degrees of separation" is the same as "distance minus one", where "distance" is the usual path length-the number of arcs in the path.) Stanley Milgram in his famous experiment challenged people to route postcards to a fixed recipient by passing them only through direct acquaintances. The average number of intermediaries on the path of the postcards lay between 4.4 and 5.7, depending on the sample of people chosen. We report the results of the first world-scale social-network graph-distance computations, using the entire Facebook network of active users (\approx721 million users, \approx69 billion friendship links). The average distance we observe is 4.74, corresponding to 3.74 intermediaries or "degrees of separation", showing that the world is even smaller than we expected, and prompting the title of this paper. More generally, we study the distance distribution of Facebook and of some interesting geographic subgraphs, looking also at their evolution over time. The networks we are able to explore are almost two orders of magnitude larger than those analysed in the previous literature. We report detailed statistical metadata showing that our measurements (which rely on probabilistic algorithms) are very accurate.
Sensing Matrix Setting Schemes for Cognitive Networks and Their Performance Analysis
Venue: arXiv cs.PF 2012
Year: 2012

Powerful spectrum decision schemes enable cognitive radios (CRs) to find transmission opportunities in spectral resources allocated exclusively to the primary users. One of the key effecting factor on the CR network throughput is the spectrum sensing sequence used by each secondary user. In this paper, secondary users' throughput maximization through finding an appropriate sensing matrix (SM) is investigated. To this end, first the average throughput of the CR network is evaluated for a given SM. Then, an optimization problem based on the maximization of the network throughput is formulated in order to find the optimal SM. As the optimum solution is very complicated, to avoid its major challenges, three novel sub optimum solutions for finding an appropriate SM are proposed for various cases including perfect and non-perfect sensing. Despite of having less computational complexities as well as lower consumed energies, the proposed solutions perform quite well compared to the optimum solution (the optimum SM). The structure and performance of the proposed SM setting schemes are discussed in detail and a set of illustrative simulation results is presented to validate their efficiencies.
Chebyshev Polynomials in Distributed Consensus Applications
Venue: arXiv cs.SY 2012
Year: 2012

In this paper we analyze the use of Chebyshev polynomials in distributed consensus applications. We study the properties of these polynomials to propose a distributed algorithm that reaches the consensus in a fast way. The algorithm is expressed in the form of a linear iteration and, at each step, the agents only require to transmit their current state to their neighbors. The difference with respect to previous approaches is that the update rule used by the network is based on the second order difference equation that describes the Chebyshev polynomials of first kind. As a consequence, we show that our algorithm achieves the consensus using far less iterations than other approaches. We characterize the main properties of the algorithm for both, fixed and switching communication topologies. The main contribution of the paper is the study of the properties of the Chebyshev polynomials in distributed consensus applications, proposing an algorithm that increases the convergence rate with respect to existing approaches. Theoretical results, as well as experiments with synthetic data, show the benefits using our algorithm.
Construction of Almost Disjunct Matrices for Group Testing
Venue: arXiv cs.IT 2012
Year: 2012

In a \emph{group testing} scheme, a set of tests is designed to identify a small number $t$ of defective items among a large set (of size $N$) of items. In the non-adaptive scenario the set of tests has to be designed in one-shot. In this setting, designing a testing scheme is equivalent to the construction of a \emph{disjunct matrix}, an $M \times N$ matrix where the union of supports of any $t$ columns does not contain the support of any other column. In principle, one wants to have such a matrix with minimum possible number $M$ of rows (tests). One of the main ways of constructing disjunct matrices relies on \emph{constant weight error-correcting codes} and their \emph{minimum distance}. In this paper, we consider a relaxed definition of a disjunct matrix known as \emph{almost disjunct matrix}. This concept is also studied under the name of \emph{weakly separated design} in the literature. The relaxed definition allows one to come up with group testing schemes where a close-to-one fraction of all possible sets of defective items are identifiable. Our main contribution is twofold. First, we go beyond the minimum distance analysis and connect the \emph{average distance} of a constant weight code to the parameters of an almost disjunct matrix constructed from it. Our second contribution is to explicitly construct almost disjunct matrices based on our average distance analysis, that have much smaller number of rows than any previous explicit construction of disjunct matrices. The parameters of our construction can be varied to cover a large range of relations for $t$ and $N$.
Evolving Chart Pattern Sensitive Neural Network Based Forex Trading Agents
Venue: arXiv cs.NE 2012
Year: 2012

Though machine learning has been applied to the foreign exchange market for algorithmic trading for quiet some time now, and neural networks(NN) have been shown to yield positive results, in most modern approaches the NN systems are optimized through traditional methods like the backpropagation algorithm for example, and their input signals are price lists, and lists composed of other technical indicator elements. The aim of this paper is twofold: the presentation and testing of the application of topology and weight evolving artificial neural network (TWEANN) systems to automated currency trading, and to demonstrate the performance when using Forex chart images as input to geometrical regularity aware indirectly encoded neural network systems, enabling them to use the patterns & trends within, when trading. This paper presents the benchmark results of NN based automated currency trading systems evolved using TWEANNs, and compares the performance and generalization capabilities of these direct encoded NNs which use the standard sliding-window based price vector inputs, and the indirect (substrate) encoded NNs which use charts as input. The TWEANN algorithm I will use in this paper to evolve these currency trading agents is the memetic algorithm based TWEANN system called Deus Ex Neural Network (DXNN) platform.
Fast Algorithms for Sparse Recovery with Perturbed Dictionary
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we account for approaches of sparse recovery from large underdetermined linear models with perturbation present in both the measurements and the dictionary matrix. Existing methods have high computation and low efficiency. The total least-squares (TLS) criterion has well-documented merits in solving linear regression problems while FOCal Underdetermined System Solver (FOCUSS) has low-computation complexity in sparse recovery. Based on TLS and FOCUSS methods, the present paper develops more fast and robust algorithms, TLS-FOCUSS and SD-FOCUSS. TLS-FOCUSS algorithm is not only near-optimum but also fast in solving TLS optimization problems under sparsity constraints, and thus fit for large scale computation. In order to reduce the complexity of algorithm further, another suboptimal algorithm named D-FOCUSS is devised. SD-FOCUSS can be applied in MMV (multiple-measurement-vectors) TLS model, which fills the gap of solving linear regression problems under sparsity constraints. The convergence of TLS-FOCUSS algorithm and SD-FOCUSS algorithm is established with mathematical proof. The simulations illustrate the advantage of TLS-FOCUSS and SD-FOCUSS in accuracy and stability, compared with other algorithms.
Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
Venue: arXiv cs.CG 2012
Year: 2012

Let G be a graph embedded on a surface of genus g with b boundary cycles. We describe algorithms to compute multiple types of non-trivial cycles in G, using different techniques depending on whether or not G is an undirected graph. If G is undirected, then we give an algorithm to compute a shortest non-separating cycle in 2^O(g) n log log n time. Similar algorithms are given to compute a shortest non-contractible or non-null-homologous cycle in 2^O(g+b) n log log n time. Our algorithms for undirected G combine an algorithm of Kutz with known techniques for efficiently enumerating homotopy classes of curves that may be shortest non-trivial cycles. Our main technical contributions in this work arise from assuming G is a directed graph with possibly asymmetric edge weights. For this case, we give an algorithm to compute a shortest non-contractible cycle in G in O((g^3 + g b)n log n) time. In order to achieve this time bound, we use a restriction of the infinite cyclic cover that may be useful in other contexts. We also describe an algorithm to compute a shortest non-null-homologous cycle in G in O((g^2 + g b)n log n) time, extending a known algorithm of Erickson to compute a shortest non-separating cycle. In both the undirected and directed cases, our algorithms improve the best time bounds known for many values of g and b.
Les crashs sont rationnels
Venue: arXiv cs.GT 2012
Year: 2012

As we show by using notions of equilibrium in infinite sequential games, crashes or financial escalations are rational for economic or environmental agents, who have a vision of an infinite world. This contradicts a picture of a self-regulating, wise and pacific economic world. In other words, in this context, equilibrium is not synonymous of stability. We try to draw, from this statement, methodological consequences and new ways of thinking, especially in economic game theory. Among those new paths, coinduction is the basis of our reasoning in infinite games.
Finding Heavy Paths in Graphs: A Rank Join Approach
Venue: arXiv cs.DB 2012
Year: 2012

Graphs have been commonly used to model many applications. A natural problem which abstracts applications such as itinerary planning, playlist recommendation, and flow analysis in information networks is that of finding the heaviest path(s) in a graph. More precisely, we can model these applications as a graph with non-negative edge weights, along with a monotone function such as sum, which aggregates edge weights into a path weight, capturing some notion of quality. We are then interested in finding the top-k heaviest simple paths, i.e., the $k$ simple (cycle-free) paths with the greatest weight, whose length equals a given parameter $\ell$. We call this the \emph{Heavy Path Problem} (HPP). It is easy to show that the problem is NP-Hard. In this work, we develop a practical approach to solve the Heavy Path problem by leveraging a strong connection with the well-known Rank Join paradigm. We first present an algorithm by adapting the Rank Join algorithm. We identify its limitations and develop a new exact algorithm called HeavyPath and a scalable heuristic algorithm. We conduct a comprehensive set of experiments on three real data sets and show that HeavyPath outperforms the baseline algorithms significantly, with respect to both $\ell$ and $k$. Further, our heuristic algorithm scales to longer lengths, finding paths that are empirically within 50% of the optimum solution or better under various settings, and takes only a fraction of the running time compared to the exact algorithm.
Rationality and Escalation in Infinite Extensive Games
Venue: arXiv cs.GT 2012
Year: 2012

The aim of this of this paper is to study infinite games and to prove formally some properties in this framework. As a consequence we show that the behavior (the madness) of people which leads to speculative crashes or escalation can be fully rational. Indeed it proceeds from the statement that resources are infinite. The reasoning is based on the concept of coinduction conceived by computer scientists to model infinite computations and used by economic agents unknowingly. When used consciously, this concept is not as simple as induction and we could paraphrase Newton: "Modeling the madness of people is more difficult than modeling the motion of planets".
Re-initialization Free Level Set Evolution via Reaction Diffusion
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents a novel reaction-diffusion (RD) method for implicit active contours, which is completely free of the costly re-initialization procedure in level set evolution (LSE). A diffusion term is introduced into LSE, resulting in a RD-LSE equation, to which a piecewise constant solution can be derived. In order to have a stable numerical solution of the RD based LSE, we propose a two-step splitting method (TSSM) to iteratively solve the RD-LSE equation: first iterating the LSE equation, and then solving the diffusion equation. The second step regularizes the level set function obtained in the first step to ensure stability, and thus the complex and costly re-initialization procedure is completely eliminated from LSE. By successfully applying diffusion to LSE, the RD-LSE model is stable by means of the simple finite difference method, which is very easy to implement. The proposed RD method can be generalized to solve the LSE for both variational level set method and PDE-based level set method. The RD-LSE method shows very good performance on boundary anti-leakage, and it can be readily extended to high dimensional level set method. The extensive and promising experimental results on synthetic and real images validate the effectiveness of the proposed RD-LSE approach.