Structural models for network dynamics typically assume a discrete timeline of network events (node activation or link creation) and a stochastic generative process giving rise to new events based on the event history and the network structure. In order to employ these models for prediction, observational data is often aggregated at a fixed temporal resolution (e.g., minutes or days). However, the underlying network processes may “speed up” or “slow down” at different points in time, rendering observations unlikely and predictions incorrect. The challenge is to optimize the timescale for the analysis of network event data, which in turn is based on structural models of the underlying network processes. We introduce the general problem of inferring the optimal temporal resolution for network event data. The goal is to map observed network events to discrete time steps by aggregation and/or disaggregation of their original timeline such that they are collectively well-explained by structural dynamics models. We unify network growth and information diffusion models and differentiate between short- and long-memory processes. We demonstrate that while optimal temporal aggregation can be performed in polynomial time, disaggregation-and thus, the general timescale inference problem-is NP-hard. We propose scalable heuristics for the problem, some with approximation guarantees, and employ them for missing event recovery and temporal link prediction, demonstrating significant improvements (absolute increase of 10% in F1 measure for event recovery and of 5% in AUC for link prediction) compared to employing the same algorithms on the default timescale of data collection.

Given a time-evolving network, how can we detect communities over periods of high internal and low external interactions? To address this question we generalize traditional local community detection in graphs to the setting of dynamic networks. Adopting existing static-network approaches in an “aggregated” graph of all temporal interactions is not appropriate for the problem as dynamic communities may be short-lived and thus lost when mixing interactions over long periods. Hence, dynamic community mining requires the detection of both the community nodes and an optimal time interval in which they are actively interacting. We propose a filter-and-verify framework for dynamic community detection. To scale to long intervals of graph evolution, we employ novel spectral bounds for dynamic community conductance and employ them to filter suboptimal periods in near-linear time. We also design a time-and-graph-aware locality sensitive hashing family to effectively spot promising community cores. Our method PHASR discovers communities of consistently higher quality (2 to 67 times better) than those of baselines. At the same time, our bounds allow for pruning between 55% and 95% of the search space, resulting in significant savings in running time compared to exhaustive alternatives for even modest time intervals of graph evolution.

Information diffusion models typically assume a discrete timeline in which an information token spreads in the network. Since users in real-world networks vary significantly in their intensity and periods of activity, our objective in this work is to answer: How to determine a temporal scale that best agrees with the observed information propagation within a network? A key limitation of existing approaches is that they aggregate the timeline into fixed-size windows, which may not fit all network nodes' activity periods. We propose the notion of a heterogeneous network clock: a mapping of events to discrete timestamps that best explains their occurrence according to a given cascade propagation model. We focus on the widely-adopted independent cascade (IC) model and formalize the optimal clock as the one that maximizes the likelihood of all observed cascades. The single optimal clock (OC) problem can be solved exactly in polynomial time. However, we prove that learning multiple optimal clocks (kOC), corresponding to temporal patterns of groups of network nodes, is NP-hard. We propose scalable solutions that run in almost linear time in the total number of cascade activations and discuss approximation guarantees for each variant. Our algorithms and their detected clocks enable improved cascade size classification (up to 8% F1 lift) and improved missing cascade data inference (0.15 better recall). We also demonstrate that the network clocks exhibit consistency within the type of content diffusing in the network and are robust with respect to the propagation probability parameters of the IC model.

MOTIVATION: Accuracy in protein design requires a fine-grained rotamer search, multiple backbone conformations, and a detailed energy function, creating a burden in runtime and memory requirements. A design task may be split into manageable pieces in both three-dimensional space and in the rotamer search space to produce small, fast jobs that are easily distributed. However, these jobs must overlap, presenting a problem in resolving conflicting solutions in the overlap regions. RESULTS: Piecemeal design, in which the design space is split into overlapping regions and rotamer search spaces, accelerates the design process whether jobs are run in series or in parallel. Large jobs that cannot fit in memory were made possible by splitting. Accepting the consensus amino acid selection in conflict regions led to non-optimal choices. Instead, conflicts were resolved using a second pass, in which the split regions were re-combined and designed as one, producing results that were closer to optimal with a minimal increase in runtime over the consensus strategy. Splitting the search space at the rotamer level instead of at the amino acid level further improved the efficiency by reducing the search space in the second pass. AVAILABILITY AND IMPLEMENTATION: Programs for splitting protein design expressions are available at www.bioinfo.rpi.edu/tools/piecemeal.html CONTACT: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.