OpenRaiser/Intern-Atlas huggingface dataset:
Opinion dynamics in social networks with stubborn agents: an issue-based perspective
Venue: arXiv cs.SY 2017
Year: 2017

Classic models on opinion dynamics usually focus on a group of agents forming their opinions interactively over single issue. Yet generally consensus can not be achieved over single issue when agents are not completely open to interpersonal influence. In this paper, opinion consensus in social networks with stubborn agents is considered over issue sequences. The social network with stubborn agents is described by the Friedkin-Johnsen (F-J) model where agents are stubborn to their initial opinions. Firstly, we propose some sufficient and necessary conditions both in terms of network topology and system matrix for convergence of the F-J model over single issue. Secondly, opinion consensus of the F-J model is investigated over issue sequences. Our analysis establishes connections between the interpersonal influence network and the network describing the relationship of agents' initial opinions for successive issues. Taking advantage of these connections, we derive the sufficient and necessary condition for the F-J model to achieve opinion consensus over issue sequences. Finally, we consider a more general scenario where each agent has bounded confidence in forming its initial opinion for every issue. By analyzing the evolution of agents' ultimate opinions for each issue over issue sequences, we prove that the connectivity of the state-dependent network is preserved in this setting. Then the conditions for agents to achieve opinion consensus over issue sequences are proposed. Simulation examples are provided to illustrate the effectiveness of our theoretical results.
C-ITS Deployment in Europe - Current Status and Outlook
Venue: arXiv cs.NI 2017
Year: 2017

Cooperative Intelligent Transport Systems (C-ITS) refers to applications using vehicle-to-vehicle and vehicle-to-infrastructure communications at a carrier frequency of 5.9 GHz to increase road traffic safety and road traffic efficiency in Europe (a.k.a. connected vehicle technology in the US). This article will shed some light on the current status of C-ITS in Europe and what is left before deployment can commence in 2019 as announced by C2C-CC. Even though there is an immense activity for the launch of C-ITS in Europe, the automotive industry is also planning for the future.
Design of a Ternary Edge-Triggered D Flip-Flap-Flop for Multiple-Valued Sequential Logic
Venue: arXiv cs.AR 2017
Year: 2017

Development of large computerized systems requires both combinational and sequential circuits. Registers and counters are two important examples of sequential circuits, which are widely used in practical applications like CPUs. The basic element of sequential logic is Flip-Flop, which stores an input value and returns two outputs (Q and Q_bar). This paper presents an innovative ternary D Flip-Flap-Flop, which offers circuit designers to customize their design by eliminating one of the outputs if it is not required. This unique feature of the new design leads to considerable power reduction in comparison with the previously presented structures. The proposed design is simulated and tested by HSPICE and 45 nm CMOS technology.
Time-Variant Graph Classification
Venue: arXiv cs.DS 2017
Year: 2017

Graphs are commonly used to represent objects, such as images and text, for pattern classification. In a dynamic world, an object may continuously evolve over time, and so does the graph extracted from the underlying object. These changes in graph structure with respect to the temporal order present a new representation of the graph, in which an object corresponds to a set of time-variant graphs. In this paper, we formulate a novel time-variant graph classification task and propose a new graph feature, called a graph-shapelet pattern, for learning and classifying time-variant graphs. Graph-shapelet patterns are compact and discriminative graph transformation subsequences. A graph-shapelet pattern can be regarded as a graphical extension of a shapelet -- a class of discriminative features designed for vector-based temporal data classification. To discover graph-shapelet patterns, we propose to convert a time-variant graph sequence into time-series data and use the discovered shapelets to find graph transformation subsequences as graph-shapelet patterns. By converting each graph-shapelet pattern into a unique tokenized graph transformation sequence, we can measure the similarity between two graph-shapelet patterns and therefore classify time-variant graphs. Experiments on both synthetic and real-world data demonstrate the superior performance of the proposed algorithms.
Steiner Network Problems on Temporal Graphs
Venue: arXiv cs.CC 2017
Year: 2017

We introduce a temporal Steiner network problem in which a graph, as well as changes to its edges and/or vertices over a set of discrete times, are given as input; the goal is to find a minimal subgraph satisfying a set of $k$ time-sensitive connectivity demands. We show that this problem, $k$-Temporal Steiner Network ($k$-TSN), is NP-hard to approximate to a factor of $k - ε$, for every fixed $k \geq 2$ and $ε> 0$. This bound is tight, as certified by a trivial approximation algorithm. Conceptually this demonstrates, in contrast to known results for traditional Steiner problems, that a time dimension adds considerable complexity even when the problem is offline. We also discuss special cases of $k$-TSN in which the graph changes satisfy a monotonicity property. We show approximation-preserving reductions from monotonic $k$-TSN to well-studied problems such as Priority Steiner Tree and Directed Steiner Tree, implying improved approximation algorithms. Lastly, $k$-TSN and its variants arise naturally in computational biology; to facilitate such applications, we devise an integer linear program for $k$-TSN based on network flows.
Finding Disjoint Paths on Edge-Colored Graphs: More Tractability Results
Venue: arXiv cs.DS 2017
Year: 2017

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (namely the number of vertices to remove to make the graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problem was known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, even in FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths.
STEM: A Scheme for Two-phase Evaluation of Majority Logic
Venue: arXiv cs.ET 2017
Year: 2017

The switching time of a magnet in a spin current based majority gate depends on the input vector combination, and this often restricts the speed of majority-based circuits. To address this issue, this work proposes a novel two-phase scheme to implement majority logic and evaluates it on an all-spin logic (ASL) majority-based logic structures. In Phase 1, the output is initialized to a preset value. Next in Phase 2, the inputs are evaluated to switch the output magnet to its correct value. The time window for the output to switch in Phase 2 is fixed. Using such a scheme, an n-input AND gate which requires a total of (2n-1) inputs in the conventional implementation can now be implemented with only (n+1) inputs. When applied to standard logic functions, it is demonstrated that the proposed method of designing ASL gates are 1.6-3.4X faster and 1.9-6.9X more energy-efficient than the conventional method, and for a five-magnet full adder, it is shown that the proposed ASL implementation is 1.5X faster, 2.2X more energy-efficient, and provides a 16% improvement in area.
A simple centrality index for scientific social recognition
Venue: arXiv cs.DL 2017
Year: 2017

We introduce a new centrality index for bipartite network of papers and authors that we call $K$-index. The $K$-index grows with the citation performance of the papers that cite a given researcher and can seen as a measure of scientific social recognition. Indeed, the $K$-index measures the number of hubs, defined in a self-consistent way in the bipartite network, that cites a given author. We show that the $K$-index can be computed by simple inspection of the Web of Science platform and presents several advantages over other centrality indexes, in particular Hirsch $h$-index. The $K$-index is robust to self-citations, is not limited by the total number of papers published by a researcher as occurs for the $h$-index and can distinguish in a consistent way researchers that have the same $h$-index but very different scientific social recognition. The $K$-index easily detects a known case of a researcher with inflated number of papers, citations and $h$-index due to scientific misconduct. Finally, we show that, in a sample of twenty-eight physics Nobel laureates and twenty-eight highly cited non-Nobel-laureate physicists, the $K$-index correlates better to the achievement of the prize than the number of papers, citations, citations per paper, citing articles or the $h$-index. Clustering researchers in a $K$ versus $h$ plot reveals interesting outliers that suggest that these two indexes can present complementary independent information.
Principled Option Learning in Markov Decision Processes
Venue: arXiv cs.LG 2017
Year: 2017

It is well known that options can make planning more efficient, among their many benefits. Thus far, algorithms for autonomously discovering a set of useful options were heuristic. Naturally, a principled way of finding a set of useful options may be more promising and insightful. In this paper we suggest a mathematical characterization of good sets of options using tools from information theory. This characterization enables us to find conditions for a set of options to be optimal and an algorithm that outputs a useful set of options and illustrate the proposed algorithm in simulation.
Preorder-Based Triangle: A Modified Version of Bilattice-Based Triangle for Belief Revision in Nonmonotonic Reasoning
Venue: arXiv cs.AI 2017
Year: 2017

Bilattice-based triangle provides an elegant algebraic structure for reasoning with vague and uncertain information. But the truth and knowledge ordering of intervals in bilattice-based triangle can not handle repetitive belief revisions which is an essential characteristic of nonmonotonic reasoning. Moreover the ordering induced over the intervals by the bilattice-based triangle is not sometimes intuitive. In this work, we construct an alternative algebraic structure, namely preorder-based triangle and we formulate proper logical connectives for this. It is also demonstrated that Preorder-based triangle serves to be a better alternative to the bilattice-based triangle for reasoning in application areas, that involve nonmonotonic fuzzy reasoning with uncertain information.
Load-aware Performance Analysis of Cell Center/Edge Users in Random HetNets
Venue: arXiv cs.IT 2017
Year: 2017

For real-time traffic, the link quality and call blocking probability (both derived from coverage probability) are realized to be poor for cell edge users (CEUs) compared to cell center users (CCUs) as the signal reception in the cell center region is better compared to the cell edge region. In heterogeneous networks (HetNets), the uncoordinated channel access by different types of base stations determine the interference statistics that further arbitrates the coverage probability. Thus, the spectrum allocation techniques have major impact on the performance of CCU and CEU. In this paper, the performance of CCUs and CEUs in a random two-tier network is studied for two spectrum allocation techniques namely: 1) co-channel (CSA), and 2) shared (SSA). For performance analysis, the widely accepted conception of modeling the tiers of HetNet using independent homogeneous Poisson point process (PPP) is considered to accommodate the spatial randomness in location of BSs. To incorporate the spatial randomness in the arrival of service and to aid the load-aware analysis, the cellular traffic is modeled using spatio-temporal PPP. Under this scenario, we have developed an analytical framework to evaluate the load-aware performance, including coverage and blocking probabilities, of CCUs and CEUs under both spectrum allocation techniques. Further, we provide insight into achievable area energy efficiency for SSA and CSA. The developed analytical framework is validated through extensive simulations. Next, we demonstrate the impact of traffic load and femto access points density on the performance of CCUs/CEUs under CSA and SSA.
Distributed Adaptive Learning of Graph Signals
Venue: arXiv cs.LG 2017
Year: 2017

The aim of this paper is to propose distributed strategies for adaptive learning of signals defined over graphs. Assuming the graph signal to be bandlimited, the method enables distributed reconstruction, with guaranteed performance in terms of mean-square error, and tracking from a limited number of sampled observations taken from a subset of vertices. A detailed mean square analysis is carried out and illustrates the role played by the sampling strategy on the performance of the proposed method. Finally, some useful strategies for distributed selection of the sampling set are provided. Several numerical results validate our theoretical findings, and illustrate the performance of the proposed method for distributed adaptive learning of signals defined over graphs.
Recognizing Detailed Human Context In-the-Wild from Smartphones and Smartwatches
Venue: arXiv cs.AI 2017
Year: 2017

The ability to automatically recognize a person's behavioral context can contribute to health monitoring, aging care and many other domains. Validating context recognition in-the-wild is crucial to promote practical applications that work in real-life settings. We collected over 300k minutes of sensor data with context labels from 60 subjects. Unlike previous studies, our subjects used their own personal phone, in any way that was convenient to them, and engaged in their routine in their natural environments. Unscripted behavior and unconstrained phone usage resulted in situations that are harder to recognize. We demonstrate how fusion of multi-modal sensors is important for resolving such cases. We present a baseline system, and encourage researchers to use our public dataset to compare methods and improve context recognition in-the-wild.
Geometry-Based Next Frame Prediction from Monocular Video
Venue: arXiv cs.LG 2017
Year: 2017

We consider the problem of next frame prediction from video input. A recurrent convolutional neural network is trained to predict depth from monocular video input, which, along with the current video image and the camera trajectory, can then be used to compute the next frame. Unlike prior next-frame prediction approaches, we take advantage of the scene geometry and use the predicted depth for generating the next frame prediction. Our approach can produce rich next frame predictions which include depth information attached to each pixel. Another novel aspect of our approach is that it predicts depth from a sequence of images (e.g. in a video), rather than from a single still image. We evaluate the proposed approach on the KITTI dataset, a standard dataset for benchmarking tasks relevant to autonomous driving. The proposed method produces results which are visually and numerically superior to existing methods that directly predict the next frame. We show that the accuracy of depth prediction improves as more prior frames are considered.
Global Versus Local Computations: Fast Computing with Identifiers
Venue: arXiv cs.CC 2017
Year: 2017

This paper studies what can be computed by using probabilistic local interactions with agents with a very restricted power in polylogarithmic parallel time. It is known that if agents are only finite state (corresponding to the Population Protocol model by Angluin et al.), then only semilinear predicates over the global input can be computed. In fact, if the population starts with a unique leader, these predicates can even be computed in a polylogarithmic parallel time. If identifiers are added (corresponding to the Community Protocol model by Guerraoui and Ruppert), then more global predicates over the input multiset can be computed. Local predicates over the input sorted according to the identifiers can also be computed, as long as the identifiers are ordered. The time of some of those predicates might require exponential parallel time. In this paper, we consider what can be computed with Community Protocol in a polylogarithmic number of parallel interactions. We introduce the class CPPL corresponding to protocols that use $O(n\log^k n)$, for some k, expected interactions to compute their predicates, or equivalently a polylogarithmic number of parallel expected interactions. We provide some computable protocols, some boundaries of the class, using the fact that the population can compute its size. We also prove two impossibility results providing some arguments showing that local computations are no longer easy: the population does not have the time to compare a linear number of consecutive identifiers. The Linearly Local languages, such that the rational language $(ab)^*$, are not computable.
An Analysis of Introductory Programming Courses at UK Universities
Venue: arXiv cs.CY 2017
Year: 2017

Context: In the context of exploring the art, science and engineering of programming, the question of which programming languages should be taught first has been fiercely debated since computer science teaching started in universities. Failure to grasp programming readily almost certainly implies failure to progress in computer science. Inquiry: What first programming languages are being taught? There have been regular national-scale surveys in Australia and New Zealand, with the only US survey reporting on a small subset of universities. This the first such national survey of universities in the UK. Approach: We report the results of the first survey of introductory programming courses (N=80) taught at UK universities as part of their first year computer science (or related) degree programmes, conducted in the first half of 2016. We report on student numbers, programming paradigm, programming languages and environment/tools used, as well as the underpinning rationale for these choices. Knowledge: The results in this first UK survey indicate a dominance of Java at a time when universities are still generally teaching students who are new to programming (and computer science), despite the fact that Python is perceived, by the same respondents, to be both easier to teach as well as to learn. Grounding: We compare the results of this survey with a related survey conducted since 2010 (as well as earlier surveys from 2001 and 2003) in Australia and New Zealand. Importance: This survey provides a starting point for valuable pedagogic baseline data for the analysis of the art, science and engineering of programming, in the context of substantial computer science curriculum reform in UK schools, as well as increasing scrutiny of teaching excellence and graduate employability for UK universities.
5G Converged Cell-less Communications in Smart Cities
Venue: arXiv cs.NI 2017
Year: 2017

Ubiquitous information service converged by different types of heterogeneous networks is one of fundamental functions for smart cities. Considering the deployment of 5G ultra-dense wireless networks, the 5G converged cell-less communication networks are proposed to support mobile terminals in smart cities. To break obstacles of heterogeneous wireless networks, the 5G converged cell-less communication network is vertically converged in different tiers of heterogeneous wireless networks and horizontally converged in celled architectures of base stations/access points. Moreover, the software defined network controllers are configured to manage the traffic scheduling and resource allocation in 5G converged cell-less communication networks. Simulation results indicate the coverage probability and the energy saving at both base stations and mobile terminals are improved by the cooperative grouping scheme in 5G converged cell-less communication networks.
A Fast Algorithm for Convolutional Structured Low-Rank Matrix Recovery
Venue: arXiv cs.NA 2017
Year: 2017

Fourier domain structured low-rank matrix priors are emerging as powerful alternatives to traditional image recovery methods such as total variation and wavelet regularization. These priors specify that a convolutional structured matrix, i.e., Toeplitz, Hankel, or their multi-level generalizations, built from Fourier data of the image should be low-rank. The main challenge in applying these schemes to large-scale problems is the computational complexity and memory demand resulting from lifting the image data to a large scale matrix. We introduce a fast and memory efficient approach called the Generic Iterative Reweighted Annihilation Filter (GIRAF) algorithm that exploits the convolutional structure of the lifted matrix to work in the original un-lifted domain, thus considerably reducing the complexity. Our experiments on the recovery of images from undersampled Fourier measurements show that the resulting algorithm is considerably faster than previously proposed algorithms, and can accommodate much larger problem sizes than previously studied.
Error Correction Coding Meets Cyber-Physical Systems: Message-Passing Analysis of Self-Healing Interdependent Networks
Venue: arXiv cs.SI 2017
Year: 2017

Coupling cyber and physical systems gives rise to numerous engineering challenges and opportunities. An important challenge is the contagion of failure from one system to another, which can lead to large-scale cascading failures. However, the self-healing ability emerges as a valuable opportunity where the overlaying cyber network can cure failures in the underlying physical network. To capture both self-healing and contagion, this paper considers a graphical model representation of an interdependent cyber-physical system, in which nodes represent various cyber or physical functionalities, and edges capture the interactions between the nodes. A message-passing algorithm is proposed for this representation to study the dynamics of failure propagation and healing. By conducting a density evolution analysis for this algorithm, network reaction to initial disruptions is investigated. It is proved that as the number of message-passing iterations increases, the network reaches a steady-state condition that would be either a complete healing or a complete collapse. Then, a sufficient condition is derived to select the network parameters to guarantee the complete healing of the system. The result of the density evolution analysis is further employed to jointly optimize the design of cyber and physical networks for maximum resiliency. This analytical framework is then extended to the cases where propagation of failures in the physical network is faster than the healing responses of the cyber network. Such scenarios are of interest in many real-life applications such as smart grid. Finally, extensive numerical results are presented to verify the analysis and investigate the impact of the network parameters on the resiliency of the network.