Search Engine Drives the Evolution of Social Networks

The search engine is tightly coupled with social networks and is primarily designed for users to acquire interested information. Specifically, the search engine assists the information dissemination for social networks, i.e., enabling users to access interested contents with keywords-searching and promoting the process of contents-transferring from the source users directly to potential interested users. Accompanying such processes, the social network evolves as new links emerge between users with common interests. However, there is no clear understanding of such a ‘chicken-and-egg’ problem, namely, new links encourage more social interactions, and vice versa. In this paper, we aim to quantitatively characterize the social network evolution phenomenon driven by a search engine. First, we propose a search network model for social network evolution. Second, we adopt two performance metrics, namely, degree distribution and network diameter. Theoretically, we prove that the degree distribution follows an intensified power-law, and the network diameter shrinks. Third, we quantitatively show that the search engine accelerates the rumor propagation in social networks. Finally, based on four real-world data sets (i.e., CDBLP, Facebook, Weibo Tweets, P2P), we verify our theoretical findings. Furthermore, we find that the search engine dramatically increases the speed of rumor propagation.

A Tutorial on Bridge Sampling

The marginal likelihood plays an important role in many areas of Bayesian statistics such as parameter estimation, model comparison, and model averaging. In most applications, however, the marginal likelihood is not analytically tractable and must be approximated using numerical methods. Here we provide a tutorial on bridge sampling (Bennett, 1976; Meng & Wong, 1996), a reliable and relatively straightforward sampling method that allows researchers to obtain the marginal likelihood for models of varying complexity. First, we introduce bridge sampling and three related sampling methods using the beta-binomial model as a running example. We then apply bridge sampling to estimate the marginal likelihood for the Expectancy Valence (EV) model—a popular model for reinforcement learning. Our results indicate that bridge sampling provides accurate estimates for both a single participant and a hierarchical version of the EV model. We conclude that bridge sampling is an attractive method for mathematical psychologists who typically aim to approximate the marginal likelihood for a limited set of possibly high-dimensional models.

Connection Scan Algorithm

We introduce the Connection Scan Algorithm (CSA) to efficiently answer queries to timetable information systems. The input consists, in the simplest setting, of a source position and a desired target position. The output consist is a sequence of vehicles such as trains or buses that a traveler should take to get from the source to the target. We study several problem variations such as the earliest arrival and profile problems. We present algorithm variants that only optimize the arrival time or additionally optimize the number of transfers in the Pareto sense. An advantage of CSA is that is can easily adjust to changes in the timetable, allowing the easy incorporation of known vehicle delays. We additionally introduce the Minimum Expected Arrival Time (MEAT) problem to handle possible, uncertain, future vehicle delays. We present a solution to the MEAT problem that is based upon CSA. Finally, we extend CSA using the multilevel overlay paradigm to answer complex queries on nation-wide integrated timetables with trains and buses.

From physical linear systems to discrete-time series. A guide for analysis of the sampled experimental data

Modelling physical data with linear discrete time series, namely Fractionally Integrated Autoregressive Moving Average (ARFIMA), is a technique which achieved attention in recent years. However, these models are used mainly as a statistical tool only, with weak emphasis on physical background of the model. The main reason for this lack of attention is that ARFIMA model describes discrete-time measurements, whereas physical models are formulated using continuous-time parameter. In order to remove this discrepancy we show that time series of this type can be regarded as sampled trajectories of the coordinates governed by system of linear stochastic differential equations with constant coefficients. The observed correspondence provides formulas linking ARFIMA parameters and the coefficients of the underlying physical stochastic system, thus providing a bridge between continuous-time linear dynamical systems and ARFIMA models.

Modeling Relational Data with Graph Convolutional Networks

Knowledge bases play a crucial role in many applications, for example question answering and information retrieval. Despite the great effort invested in creating and maintaining them, even the largest representatives (e.g., Yago, DBPedia or Wikidata) are highly incomplete. We introduce relational graph convolutional networks (R-GCNs) and apply them to two standard knowledge base completion tasks: link prediction (recovery of missing facts, i.e. subject-predicate-object triples) and entity classification (recovery of missing attributes of entities). R-GCNs are a generalization of graph convolutional networks, a recent class of neural networks operating on graphs, and are developed specifically to deal with highly multi-relational data, characteristic of realistic knowledge bases. Our methods achieve competitive results on standard benchmarks for both tasks.

Resolving Stanley’s e-positivity of claw-contractible-free graphs

Distributed Multi-Speaker Voice Activity Detection for Wireless Acoustic Sensor Networks

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

Low-rank and Sparse NMF for Joint Endmembers’ Number Estimation and Blind Unmixing of Hyperspectral Images

Non-normal limiting distribution for optimal alignment scores of strings in binary alphabets

Laplacian, on the Sierpinski tetrahedron

Incorporating Covariates into Integrated Factor Analysis of Multi-View Data

A new sample-based algorithms to compute the total sensitivity index

Reservoir Computing and Extreme Learning Machines using Pairs of Cellular Automata Rules

Control and State Estimation of the One-Phase Stefan Problem via Backstepping Design

The Beta Flexible Weibull Distribution

Particle Value Functions

Automatically identifying wild animals in camera trap images with deep learning

The circular law for random regular digraphs

Conditional Accelerated Lazy Stochastic Gradient Descent

Adaptivity to Noise Parameters in Nonparametric Active Learning

Fractality in nonequilibrium steady states of quasiperiodic systems

Causal Inference through the Method of Direct Estimation

Temporal Information Extraction for Question Answering Using Syntactic Dependencies in an LSTM-based Architecture

Uniform Diameter Bounds in Branch Groups

Towards Closing the Energy Gap Between HOG and CNN Features for Embedded Vision

More restricted growth functions: Gray codes and exhaustive generations

Tensor Product of Polygonal Cell Complexes

An Improved Bound for Upper Domination of Cartesian Products of Graphs

Invertibility of graph translation and support of Laplacian Fiedler vectors

Understanding Traffic Density from Large-Scale Web Camera Data

DropRegion Training of Inception Font Network for High-Performance Chinese Font Recognition

Empirical Evaluation of Parallel Training Algorithms on Acoustic Modeling

Complexity of Correspondence Homomorphisms

Need for Speed: A Benchmark for Higher Frame Rate Object Tracking

Resilient Transmission Grid Design: AC Relaxation vs. DC approximation

Decomposition analysis to identify intervention targets for reducing disparities

On rate of convergence in non-central limit theorems

A Contract-based Incentive Mechanism for Energy Harvesting-based Internet of Things

Learning Robust Visual-Semantic Embeddings

Computer Aided Detection of Anemia-like Pallor

Construction of a Japanese Word Similarity Dataset

Unsupervised Anomaly Detection with Generative Adversarial Networks to Guide Marker Discovery

Quantifying the causal effect of speed cameras on road traffic accidents via an approximate Bayesian doubly robust estimator

Completely regular codes by concatenating Hamming codes

A Tight Upper Bound on the Second-Order Coding Rate of Parallel Gaussian Channels with Feedback

A note on relationship between some bounding inequalities in stability analysis of time-delay systems

The dynamics of power laws: Fitness and aging in preferential attachment trees

A Novel Robust Transceiver Design for MIMO Interference Channel

Symbolic computation with monotone operators

On weighted occupation times for refracted spectrally negative Lévy processes

Implicit Gradient Neural Networks with a Positive-Definite Mass Matrix for Online Linear Equations Solving

A characterization of circle graphs in terms of multimatroid representations

A Gröbner basis for the graph of the reciprocal plane

Michell trusses in two dimensions as a Gamma-limit of optimal design problems in linear elasticity

Comparison of Different Methods for Tissue Segmentation in Histopathological Whole-Slide Images

Energy Efficient Precoding C-RAN Downlink with Compression at Fronthaul

Auxiliary Manifold Embedding for Fully Convolutional Networks

The use of spatial information in entropy measures

Color Orchestra: Ordering Color Palettes for Interpolation and Prediction

Approximate probabilistic cellular automata for the dynamics of single-species populations under discrete logistic-like growth with and without weak Allee effects

Globally Optimal Beamforming Design for Downlink CoMP transmission with Limited Backhaul Capacity

Hidden Order behind Two Dimensional Random Vortices

Towards Diverse and Natural Image Descriptions via a Conditional GAN

Modeling spatial processes with unknown extremal dependence class

On the super domination number of lexicographic product graphs

On the Enumeration of Circulant Graphs of Prime-Power Order: the case of $p^3$

Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

Pattern representation and recognition with accelerated analog neuromorphic systems

Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks

Exact distance coloring in trees

An FPTAS for the Knapsack Problem with Parametric Weights

Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint

Probabilistic characterizations of essential self-adjointness and removability of singularities

Computation Peer Offloading for Energy-Constrained Mobile Edge Computing in Small-Cell Networks

Online Learning for Offloading and Autoscaling in Energy Harvesting Mobile Edge Computing

Approximation ratio of RePair

Block CUR : Decomposing Large Distributed Matrices

PSF field learning based on Optimal Transport Distances

Performance Analysis of Ultra-Dense Networks with Elevated Base Stations

Robust Assignments with Vulnerable Nodes

Propensity score weighting for causal inference with clustered data

On the size of the block of 1 for $Ξ$-coalescents with dust

A minimally invasive neurostimulation method for controlling epilepsy seizures

Analysis of the Gibbs Sampler for Gaussian hierarchical models via multigrid decomposition

Nonconvex One-bit Single-label Multi-label Learning

Global Entity Ranking Across Multiple Languages

A conjecture on determining which $(n,k)$-star graphs are not Cayley graphs

Mixing time of Markov chains for the uniform 1-2 model

Tusnády’s problem, the transference principle, and non-uniform QMC sampling

On the Minimization of Convex Functionals of Probability Distributions Under Band Constraints

Communication Primitives in Cognitive Radio Networks

Inference via low-dimensional couplings