OpenRaiser/Intern-Atlas huggingface dataset:
Benchmarking Measures of Network Influence
Venue: arXiv cs.SI 2016
Year: 2016

Identifying key agents for the transmission of diseases (ideas, technology, etc.) across social networks has predominantly relied on measures of centrality on a static base network or a temporally flattened graph of agent interactions. Various measures have been proposed as the best trackers of influence, such as degree centrality, betweenness, and $k$-shell, depending on the structure of the connectivity. We consider SIR and SIS propagation dynamics on a temporally-extruded network of observed interactions and measure the conditional marginal spread as the change in the magnitude of the infection given the removal of each agent at each time: its temporal knockout (TKO) score. We argue that the exhaustive approach of the TKO score makes it an effective benchmark measure for evaluating the accuracy of other, often more practical, measures of influence. We find that none of the common network measures applied to the induced flat graphs are accurate predictors of network propagation influence on the systems studied; however, temporal networks and the TKO measure provide the requisite targets for the hunt for effective predictive measures.
Overview of Annotation Creation: Processes & Tools
Venue: arXiv cs.CL 2016
Year: 2016

Creating linguistic annotations requires more than just a reliable annotation scheme. Annotation can be a complex endeavour potentially involving many people, stages, and tools. This chapter outlines the process of creating end-to-end linguistic annotations, identifying specific tasks that researchers often perform. Because tool support is so central to achieving high quality, reusable annotations with low cost, the focus is on identifying capabilities that are necessary or useful for annotation tools, as well as common problems these tools present that reduce their utility. Although examples of specific tools are provided in many cases, this chapter concentrates more on abstract capabilities and problems because new tools appear continuously, while old tools disappear into disuse or disrepair. The two core capabilities tools must have are support for the chosen annotation scheme and the ability to work on the language under study. Additional capabilities are organized into three categories: those that are widely provided; those that often useful but found in only a few tools; and those that have as yet little or no available tool support.
The coalescing-branching random walk on expanders and the dual epidemic process
Venue: arXiv cs.DC 2016
Year: 2016

Information propagation on graphs is a fundamental topic in distributed computing. One of the simplest models of information propagation is the push protocol in which at each round each agent independently pushes the current knowledge to a random neighbour. In this paper we study the so-called coalescing-branching random walk (COBRA), in which each vertex pushes the information to $k$ randomly selected neighbours and then stops passing information until it receives the information again. The aim of COBRA is to propagate information fast but with a limited number of transmissions per vertex per step. In this paper we study the cover time of the COBRA process defined as the minimum time until each vertex has received the information at least once. Our main result says that if $G$ is an $n$-vertex $r$-regular graph whose transition matrix has second eigenvalue $λ$, then the COBRA cover time of $G$ is $\mathcal O(\log n )$, if $1-λ$ is greater than a positive constant, and $\mathcal O((\log n)/(1-λ)^3))$, if $1-λ\gg \sqrt{\log( n)/n}$. These bounds are independent of $r$ and hold for $3 \le r \le n-1$. They improve the previous bound of $O(\log^2 n)$ for expander graphs. Our main tool in analysing the COBRA process is a novel duality relation between this process and a discrete epidemic process, which we call a biased infection with persistent source (BIPS). A fixed vertex $v$ is the source of an infection and remains permanently infected. At each step each vertex $u$ other than $v$ selects $k$ neighbours, independently and uniformly, and $u$ is infected in this step if and only if at least one of the selected neighbours has been infected in the previous step. We show the duality between COBRA and BIPS which says that the time to infect the whole graph in the BIPS process is of the same order as the cover time of the COBRA process
Cognitive Network Cooperation for Green Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

In recent years, there has been a growing interest in green cellular networks for the sake of reducing the energy dissipated by communications and networking devices, including the base stations (BSs) and battery-powered user terminals (UTs). This paper investigates the joint employment of cognition and cooperation techniques invoked for improving the energy efficiency of cellular networks. To be specific, the cellular devices first have to identify the unused spectral bands (known as spectrum holes) using their spectrum sensing functionality. Then, they cooperate for exploiting the detected spectrum holes to support energy-efficient cellular communications. Considering the fact that contemporary terminals (e.g., smart phones) support various wireless access interfaces, we exploit either the Bluetooth or the Wi-Fi network operating within the spectrum holes for supporting cellular communications with the intention of achieving energy savings. This approach is termed as \emph{cognitive network cooperation}, since different wireless access networks cognitively cooperate with cellular networks. In order to illustrate the energy efficiency benefits of using both cognition and cooperation, we study the cooperation between television stations (TVSs) and BSs in transmitting to UTs relying on an opportunistic exploitation of the TV spectrum, where the unused TV spectral band is utilized in an opportunistic way, depending on whether it is detected to be idle (or not). It is shown that for a given number of information bits to be transmitted, the total energy consumed is significantly reduced, when both cognition and cooperation are supported in cellular networks, as compared to the conventional direct transmission, pure cognition and pure cooperation.
XBF: Scaling up Bloom-filter-based Source Routing
Venue: arXiv cs.NI 2016
Year: 2016

A well known drawback of IP-multicast is that it requires per-group state to be stored in the routers. Bloom-filter based source-routed multicast remedies this problem by moving the state from the routers to the packets. However, a fixed sized Bloom-filter can only store a limited number of items before the false positive ratio grows too high implying scalability issues. Several proposals have tried to address these scalability issues in Bloom-filter forwarding. These proposals, however, unnecessarily increase the forwarding complexity. In this paper, we present Extensible-Bloom-filter (XBF), a new framing and forwarding solution which effectively circumvents the aforementioned drawbacks. XBF partitions a network into sub-networks that reflect the network topology and traffic patterns, and uses a separate fixed-length Bloom-filter in each of these. We formulate this partition assignment problem into a balanced edge partitioning problem, and evaluate it with simulations on realistic topologies. Our results show that XBF scales to very large networks with minimal overhead and completely eliminates the false-positives that have plagued the traditional Bloom-filter-based forwarding protocols. It furthermore integrates with SDN environments, making it highly suitable for deployments in off-the-shelf SDN-based networks.
An algorithm for the weighted metric dimension of two-dimensional grids
Venue: arXiv cs.DS 2016
Year: 2016

A two-dimensional grid consists of vertices of the form (i,j) for 1 \leq i \leq m and 1 \leq j \leq n, for fixed m,n > 1. Two vertices are adjacent if the \ell_1 distance between their vectors is equal to 1. A landmark set is a subset of vertices L \subseteq V, such that for any distinct pair of vertices u,v \in V, there exists a vertex of L whose distances to u and v are not equal. We design an efficient algorithm for finding a minimum landmark set with respect to total cost in a grid graph with non-negative costs defined on the vertices.
Spectral Learning for Supervised Topic Models
Venue: arXiv cs.LG 2016
Year: 2016

Supervised topic models simultaneously model the latent topic structure of large collections of documents and a response variable associated with each document. Existing inference methods are based on variational approximation or Monte Carlo sampling, which often suffers from the local minimum defect. Spectral methods have been applied to learn unsupervised topic models, such as latent Dirichlet allocation (LDA), with provable guarantees. This paper investigates the possibility of applying spectral methods to recover the parameters of supervised LDA (sLDA). We first present a two-stage spectral method, which recovers the parameters of LDA followed by a power update method to recover the regression model parameters. Then, we further present a single-phase spectral algorithm to jointly recover the topic distribution matrix as well as the regression weights. Our spectral algorithms are provably correct and computationally efficient. We prove a sample complexity bound for each algorithm and subsequently derive a sufficient condition for the identifiability of sLDA. Thorough experiments on synthetic and real-world datasets verify the theory and demonstrate the practical effectiveness of the spectral algorithms. In fact, our results on a large-scale review rating dataset demonstrate that our single-phase spectral algorithm alone gets comparable or even better performance than state-of-the-art methods, while previous work on spectral methods has rarely reported such promising performance.
Strong Backdoors for Default Logic
Venue: arXiv cs.LO 2016
Year: 2016

In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, identity). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-DP2 , or in para-NP, depending on the target class.
Pricing and Resource Allocation via Game Theory for a Small-Cell Video Caching System
Venue: arXiv cs.IT 2016
Year: 2016

Evidence indicates that downloading on-demand videos accounts for a dramatic increase in data traffic over cellular networks. Caching popular videos in the storage of small-cell base stations (SBS), namely, small-cell caching, is an efficient technology for reducing the transmission latency whilst mitigating the redundant transmissions of popular videos over back-haul channels. In this paper, we consider a commercialized small-cell caching system consisting of a network service provider (NSP), several video retailers (VR), and mobile users (MU). The NSP leases its SBSs to the VRs for the purpose of making profits, and the VRs, after storing popular videos in the rented SBSs, can provide faster local video transmissions to the MUs, thereby gaining more profits. We conceive this system within the framework of Stackelberg game by treating the SBSs as a specific type of resources. We first model the MUs and SBSs as two independent Poisson point processes, and develop, via stochastic geometry theory, the probability of the specific event that an MU obtains the video of its choice directly from the memory of an SBS. Then, based on the probability derived, we formulate a Stackelberg game to jointly maximize the average profit of both the NSP and the VRs. Also, we investigate the Stackelberg equilibrium by solving a non-convex optimization problem. With the aid of this game theoretic framework, we shed light on the relationship between four important factors: the optimal pricing of leasing an SBS, the SBSs allocation among the VRs, the storage size of the SBSs, and the popularity distribution of the VRs. Monte-Carlo simulations show that our stochastic geometry-based analytical results closely match the empirical ones. Numerical results are also provided for quantifying the proposed game-theoretic framework by showing its efficiency on pricing and resource allocation.
Vertex-disjoint Cycle Cover for graph signal processing
Venue: arXiv cs.IT 2016
Year: 2016

Eigenvectors of the Laplacian of a cycle graph exhibit the sinusoidal characteristics of the standard DFT basis, and signals defined on such graphs are amenable to linear shift invariant (LSI) operations. In this paper we propose to reduce a generic graph to its vertex-disjoint cycle cover, i.e., a set of subgraphs that are cycles, that together contain all vertices of the graph, and no two subgraphs have any vertices in common. Additionally if the weight of an edge in the graph is a function of the variation in the signals on its vertices, then maximally smooth cycles can be found, such that the resulting DFT does not have high frequency components. We show that an image graph can be reduced to such low-frequency cycles, and use that to propose a simple image denoising algorithm.
On the scaling of functional spaces, from smart cities to cloud computing
Venue: arXiv cs.CY 2016
Year: 2016

The study of spacetime, and its role in understanding functional systems has received little attention in information science. Recent work, on the origin of universal scaling in cities and biological systems, provides an intriguing insight into the functional use of space, and its measurable effects. Cities are large information systems, with many similarities to other technological infrastructures, so the results shed new light indirectly on the scaling the expected behaviour of smart pervasive infrastructures and the communities that make use of them. Using promise theory, I derive and extend the scaling laws for cities to expose what may be extrapolated to technological systems. From the promise model, I propose an explanation for some anomalous exponents in the original work, and discuss what changes may be expected due to technological advancement.
Multiscale Analysis of Information Dynamics for Linear Multivariate Processes
Venue: arXiv cs.IT 2016
Year: 2016

In the study of complex physical and physiological systems represented by multivariate time series, an issue of great interest is the description of the system dynamics over a range of different temporal scales. While information-theoretic approaches to the multiscale analysis of complex dynamics are being increasingly used, the theoretical properties of the applied measures are poorly understood. This study introduces for the first time a framework for the analytical computation of information dynamics for linear multivariate stochastic processes explored at different time scales. After showing that the multiscale processing of a vector autoregressive (VAR) process introduces a moving average (MA) component, we describe how to represent the resulting VARMA process using state-space (SS) models and how to exploit the SS model parameters to compute analytical measures of information storage and information transfer for the original and rescaled processes. The framework is then used to quantify multiscale information dynamics for simulated unidirectionally and bidirectionally coupled VAR processes, showing that rescaling may lead to insightful patterns of information storage and transfer but also to potentially misleading behaviors.
Deployment of 5G Networking Infrastructure with Machine Type Communication Considerations
Venue: arXiv cs.IT 2016
Year: 2016

Designing optimal strategies to deploy small cell stations is crucial to meet the quality-of-service requirements in next-generation cellular networks with constrained deployment costs. In this paper, a general deployment framework is proposed to jointly optimize the locations of backhaul aggregate nodes, small base stations, machine aggregators, and multi-hop wireless backhaul links to accommodate both human-type and machine-type communications. The goal is to provide deployment solutions with best coverage performance under cost constraints. The formulated problem is shown to be a multi-objective integer programming for which it is challenging to obtain the optimal solutions. To solve the problem, a heuristic algorithm is proposed by combining Lagrangian relaxation, the weighted sum method, the $ε$-constraint method and tabu search to obtain both the solutions and bounds, for the objective function. Simulation results show that the proposed framework can provide solutions with better performance compared with conventional deployment models in scenarios where available fiber connections are scarce. Furthermore, the gap between obtained solutions and the lower bounds is quite tight.
Endofunctors modelling higher-order behaviours
Venue: arXiv cs.LO 2016
Year: 2016

In this paper we show how the abstract behaviours of higher-order systems can be modelled as final coalgebras of suitable behavioural functors. These functors have the challenging peculiarity to be circularly defined with their own final coalgebra. Our main contribution is a general construction for defining these functors, solving this circularity which is the essence of higher-order behaviours. This characterisation is syntax agnostic. To achieve this property, we shift from term passing to behaviour passing: in the former higher-order is expressed by passing around syntactic objects (such as terms or processes) as representations of behaviours whereas the former ditches the syntactic encoding altogether and works directly with behaviours i.e. semantic objects. From this perspective, the former can be seen as syntactic higher-order whereas the later as semantic higher-order.
On a recursive construction of circular paths and the search for $π$ on the integer lattice $\mathbb{Z}^2$
Venue: arXiv cs.GR 2016
Year: 2016

Digital circles not only play an important role in various technological settings, but also provide a lively playground for more fundamental number-theoretical questions. In this paper, we present a new recursive algorithm for the construction of digital circles on the integer lattice $\mathbb{Z}^2$, which makes sole use of the signum function. By briefly elaborating on the nature of discretization of circular paths, we then find that this algorithm recovers, in a space endowed with $\ell^1$-norm, the defining constant $π$ of a circle in $\mathbb{R}^2$.
Scaffoldings and Spines: Organizing High-Dimensional Data Using Cover Trees, Local Principal Component Analysis, and Persistent Homology
Venue: arXiv cs.CG 2016
Year: 2016

We propose a flexible and multi-scale method for organizing, visualizing, and understanding datasets sampled from or near stratified spaces. The first part of the algorithm produces a cover tree using adaptive thresholds based on a combination of multi-scale local principal component analysis and topological data analysis. The resulting cover tree nodes consist of points within or near the same stratum of the stratified space. They are then connected to form a \emph{scaffolding} graph, which is then simplified and collapsed down into a \emph{spine} graph. From this latter graph the stratified structure becomes apparent. We demonstrate our technique on several synthetic point cloud examples and we use it to understand song structure in musical audio data.
Computing halting probabilities from other halting probabilities
Venue: arXiv cs.CC 2016
Year: 2016

The halting probability of a Turing machine is the probability that the machine will halt if it starts with a random stream written on its one-way input tape. When the machine is universal, this probability is referred to as Chaitin's omega number, and is the most well known example of a real which is random in the sense of Martin-Löf. Although omega numbers depend on the underlying universal Turing machine, they are robust in the sense that they all have the same Turing degree, namely the degree of the halting problem. In this paper we give precise bounds on the redundancy growth rate that is generally required for the computation of an omega number from another omega number. We show that for each $ε>1$, any pair of omega numbers compute each other with redundancy $ε\log n$. On the other hand, this is not true for $ε=1$. In fact, we show that for each omega number there exists another omega number which is not computable from the first one with redundancy $\log n$. This latter result improves an older result of Frank Stephan.
Restricted $q$-Isometry Properties Adapted to Frames for Nonconvex $l_q$-Analysis
Venue: arXiv cs.IT 2016
Year: 2016

This paper discusses reconstruction of signals from few measurements in the situation that signals are sparse or approximately sparse in terms of a general frame via the $l_q$-analysis optimization with $0<q\leq 1$. We first introduce a notion of restricted $q$-isometry property ($q$-RIP) adapted to a dictionary, which is a natural extension of the standard $q$-RIP, and establish a generalized $q$-RIP condition for approximate reconstruction of signals via the $l_q$-analysis optimization. We then determine how many random, Gaussian measurements are needed for the condition to hold with high probability. The resulting sufficient condition is met by fewer measurements for smaller $q$ than when $q=1$. The introduced generalized $q$-RIP is also useful in compressed data separation. In compressed data separation, one considers the problem of reconstruction of signals' distinct subcomponents, which are (approximately) sparse in morphologically different dictionaries, from few measurements. With the notion of generalized $q$-RIP, we show that under an usual assumption that the dictionaries satisfy a mutual coherence condition, the $l_q$ split analysis with $0<q\leq1 $ can approximately reconstruct the distinct components from fewer random Gaussian measurements with small $q$ than when $q=1$
graphVizdb: A Scalable Platform for Interactive Large Graph Visualization
Venue: arXiv cs.HC 2016
Year: 2016

We present a novel platform for the interactive visualization of very large graphs. The platform enables the user to interact with the visualized graph in a way that is very similar to the exploration of maps at multiple levels. Our approach involves an offline preprocessing phase that builds the layout of the graph by assigning coordinates to its nodes with respect to a Euclidean plane. The respective points are indexed with a spatial data structure, i.e., an R-tree, and stored in a database. Multiple abstraction layers of the graph based on various criteria are also created offline, and they are indexed similarly so that the user can explore the dataset at different levels of granularity, depending on her particular needs. Then, our system translates user operations into simple and very efficient spatial operations (i.e., window queries) in the backend. This technique allows for a fine-grained access to very large graphs with extremely low latency and memory requirements and without compromising the functionality of the tool. Our web-based prototype supports three main operations: (1) interactive navigation, (2) multi-level exploration, and (3) keyword search on the graph metadata.