The sparse dictionary coding framework represents signals as a linear combination of a few predefined dictionary atoms. It has been employed for images, time series, graph signals and recently for 2-way (or 2D) spatio-temporal data employing jointly temporal and spatial dictionaries. Large and over-complete dictionaries enable high-quality models, but also pose scalability challenges which are exacerbated in multi-dictionary settings. Hence, an important problem that we address in this paper is: How to scale multi-dictionary coding for large dictionaries and datasets?We propose a multi-dictionary atom selection technique for low-rank sparse coding named LRMDS. To enable scalability to large dictionaries and datasets, it progressively selects groups of row-column atom pairs based on their alignment with the data and performs convex relaxation coding via the corresponding sub-dictionaries. We demonstrate both theoretically and experimentally that when the data has a low-rank encoding with a sparse subset of the atoms, LRMDS is able to select them with strong guarantees under mild assumptions. Furthermore, we demonstrate the scalability and quality of LRMDS in both synthetic and real-world datasets and for a range of coding dictionaries. It achieves 3 times to 10 times speed-up compared to baselines, while obtaining up to two orders of magnitude improvement in representation quality on some of the real world datasets given a fixed target number of atoms.

Tensor decomposition methods are popular tools for analysis of multi-way datasets from the social media, healthcare, spatio-temporal domains, and others. Widely adopted models such as Tucker and canonical polyadic decomposition (CPD) follow a data-driven philosophy: they decompose a tensor into factors that approximate the observed data well. In some cases side information is available about the tensor modes. For example, in a temporal user-item purchases tensor a user influence graph, an item similarity graph, and knowledge about seasonality or trends in the temporal mode may be available. Such side information may enable more succinct and interpretable tensor decomposition models and improved quality in downstream tasks. We propose a framework for Multi-Dictionary Tensor Decomposition (MDTD) which takes advantage of prior structural information about tensor modes in the form of coding dictionaries to obtain sparsely coded tensor factors. We derive a general optimization algorithm for MDTD that handles both complete inputs and inputs with missing values. MDTD handles large sparse tensors typical in many real-world application domains. We experimentally demonstrate its utility in both synthetic and real-world datasets. It learns more concise models than dictionary-free counterparts and improves (i) reconstruction quality (up to 60% smaller models coupled with reduced representation error); (ii) missing values imputation quality (two-fold MSE reduction with up to orders of magnitude time savings) and (iii) the estimation of the tensor rank. MDTD’s quality improvements do not come with a running time premium: it can decompose 19GB datasets in less than a minute. It can also impute missing values in sparse billion-entry tensors more accurately and scalably than state-of-the-art competitors.

Machine learning and data analytics tasks on graphs enjoy a lot of attention from both researchers and practitioners due to the utility that a graph structure among data entities adds for downstream tasks. In many cases, however, a graph structure is not known a priori, and instead has to be inferred from data. Specifically, learning a graph associating time series may elucidate hidden dependencies and also enable improved performance in tasks like classification, forecasting and clustering. While approaches based on pairwise correlation and precision matrix estimation have been employed widely, recent approaches that model observations as signals on graphs have been shown to be more advantageous.

Dynamic interaction data is often aggregated in a sequence of network snapshots before being employed in downstream analysis. The two common ways of defining network snapshots are i) a fixed time interval or ii) fixed number of interactions per snapshot. The choice of aggregation has a significant impact on subsequent analysis, and it is not trivial to select one approach over another for a given dataset. More importantly assuming snapshot regularity is data-agnostic and may be at odds with the underlying interaction dynamics. To address these challenges, we propose a method for community-aware detection of network states (CADENCE) based on the premise of stable interaction time-frames within network communities. We simultaneously detect network communities and partition the global interaction activity into scale-adaptive snapshots where the level of interaction within communities remains stable. We model a temporal network as a node-node-time tensor and use a structured canonical polyadic decomposition with a piece-wise constant temporal factor to iteratively identify communities and their activity levels. We demonstrate that transitions between network snapshots learned by CADENCE constitute network change points of better quality than those predicted by state-of-the-art network change point detectors. Furthermore, the network structure within individual snapshots reflects ground truth communities better than baselines for adaptive tensor granularity. Through a case study on a real-world Reddit dataset, we showcase the interpretability of CADENCE motivated snapshots as periods separated by significant events.

Unlike tabular data, features in network data are interconnected within a domain-specific graph. Examples of this setting include gene expression overlaid on a protein interaction network (PPI) and user opinions in a social network. Network data is typically high-dimensional (large number of nodes) and often contains outlier snapshot instances and noise. In addition, it is often non-trivial and time-consuming to annotate instances with global labels (e.g., disease or normal). How can we jointly select discriminative subnetworks and representative instances for network data without supervision?We address these challenges within an unsupervised framework for joint subnetwork and instance selection in network data, called UISS, via a convex self-representation objective. Given an unlabeled network dataset, UISS identifies representative instances while ignoring outliers. It outperforms state-of-the-art baselines on both discriminative subnetwork selection and representative instance selection, achieving up to 10% accuracy improvement on all real-world data sets we use for evaluation. When employed for exploratory analysis in RNA-seq network samples from multiple studies it produces interpretable and informative summaries.

DNA-stabilized silver nanoclusters (AgN-DNAs) are a class of nanomaterials comprised of 10-30 silver atoms held together by short synthetic DNA template strands. AgN-DNAs are promising biosensors and fluorophores due to their small sizes, natural compatibility with DNA, and bright fluorescence---the property of absorbing light and re-emitting light of a different color. The sequence of the DNA template acts as a "genome" for AgN-DNAs, tuning the size of the encapsulated silver nanocluster, and thus its fluorescence color. However, current understanding of the AgN-DNA genome is still limited. Only a minority of DNA sequences produce highly fluorescent AgN-DNAs, and the bulky DNA strands and complex DNA-silver interactions make it challenging to use first principles chemical calculations to understand and design AgN-DNAs. Thus, a major challenge for researchers studying these nanomaterials is to develop methods to employ observational data about studied AgN-DNAs to design new nanoclusters for targeted applications.

Graphs are widely employed models for structural dependencies in complex systems such as social, infrastructure, and information networks. Graph datasets are often massive, computationally challenging to mine, and non-trivial to understand by humans. Hence, there is a large body of literature on graph summarization aiming to improve algorithmic efficiency, quality of analytics tasks, and visualization. Most existing graph summarization methods focus solely on the structure of the graph and assume that node properties are static. In this paper we focus on graphs with temporal measurements on their nodes, which we call temporal graph signals. Our goal is to learn a graph aggregation (summary) that best reflects both the structure and the temporal node measurements. We propose a signal-aware graph aggregation framework called SAGA. The key idea is to group well-connected nodes whose behavior exhibits consistent temporal patterns. SAGA learns simultaneously how to (i) aggregate the graph into supernode groups and (ii) represent the groups' collective temporal behavior succinctly via a sparse dictionary encoding. The obtained aggregations offer insights into the functional organization of the graph and the learned model enables improved performance for state-of-the-art approaches for downstream tasks like temporal graph signal decomposition, forecasting and link prediction. We demonstrate, in both synthetic and real-world data sets, that SAGA's learned aggregations improve (i) reconstruction quality for temporal graph signals by up to 75%, (ii) link prediction accuracy by up to 40% and (iii) the accuracy of forecasting by up to 63% while also offering 50% scalability improvements.

Empirical studies and theoretical models both highlight burstinessas a common temporal pattern in online behavior. A key driver for burstiness is the self-exciting nature of online interactions. For example, posts in online groups often incite posts in response. Such temporal dependencies are easily lost when interaction data is aggregated in snapshots which are subsequently analyzed independently. An alternative is to model individual interactions as a multi-dimensional self-exciting process, thus, enforcing both temporal and network dependencies. Point processes, however, are challenging to employ for large real-world datasets as fitting them incurs super-linear cost in the number of events. How can we efficiently detect online groups exhibiting bursty self-exciting temporal behavior in large real-world datasets?

Temporal graph signals are multivariate time series with individual components associated with nodes of a fixed graph structure. Data of this kind arises in many domains including activity of social network users, sensor network readings over time, and time course gene expression within the interaction network of a model organism. Traditional matrix decomposition methods applied to such data fall short of exploiting structural regularities encoded in the underlying graph and also in the temporal patterns of the signal. How can we take into account such structure to obtain a succinct and interpretable representation of temporal graph signals?

Natural and human-engineered systems often exhibit periodic behavior. Examples include the climate system, migration of animals in the wild, consumption of electricity in the power grid and others. The behavior of such systems, however, is not perfectly periodic. The time series we collect from them are often noisy and incomplete due to limitations of data collection and transmission, or due to sensor malfunction and outages. In addition, there are often multiple periods, for example, air temperature and pressure oscillates daily and yearly with the seasons. Hence, accurate and robust period estimation from raw time series is a fundamental task often employed in downstream applications such as traffic prediction and anomaly detection.In this paper, we study the period estimation problem in noisy time series with multiple periods and missing values. We propose a method based on a Ramanujan periodic dictionary and a vector completion model to estimate missing values. To account for the block structure in the Ramanujan periodic dictionary, we introduce a graph Laplacian group lasso regularization which enables robust and efficient period learning in the presence of missing observations. In our extensive experiments on datasets from diverse domains, our proposed methodology outperforms state-of-art baselines in terms of accuracy of period estimation.

Modeling and detection of seasonality in time series is essential for accurate analysis, prediction and anomaly detection. Examples of seasonal effects at different scales abound: the increase in consumer product sales during the holiday season recurs yearly, and similarly household electricity usage has daily, weekly and yearly cycles. The period in real-world time series, however, may be obfuscated by noise and missing values arising in data acquisition. How can one learn the natural periodicity from incomplete multivariate time series? We propose a robust framework for multivariate period detection, called LAPIS. It encodes incomplete and noisy data as a sparse summary via a Ramanujan periodic dictionary. LAPIS can accurately detect a mixture of multiple periods in the same time series even when 70% of the observations are missing. A key innovation of our framework is that it exploits shared periods across individual time series even when they are not correlated or in-phase. Beyond detecting periods, LAPIS enables improvements in downstream applications such as forecasting, missing value imputation and clustering. At the same time our approach scales to large real-world data executing within seconds on datasets of length up to half a million time points.

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.

Many complex networked systems, both natural and human-made, exhibit periodic behavior driven by underlying seasonal processes: election cycles and regular sporting events in social networks, cell cycle phases in gene networks, and load variation in infrastructure networks due to weather or daylight patterns. The “natural” periodicity may vary across network communities. At the same time this periodic community behavior is central to (i) understating the overall system dynamics and (ii) for detection of the communities themselves. The predominant approach to dynamic community detection first detects communities and then as a second step quantify seasonality in their activity. How to jointly detect communities and their inherent periodicity, while also accounting for non-periodic one-off events? We propose PERCeIDs, a framework for periodic overlapping community detection from temporal interaction data. We model observed pairwise interaction activity as a mixture of periodic and outlier (non-periodic) components. We explicitly enforce periodic structure within our model by learning a succinct Ramanujan basis dictionary for community behaviors. By explicitly modeling periodicity, PERCeIDs outperforms baselines on both detecting highly overlapping communities with up to 2fold improvement in NMI compared to state-of-the-art baselines, while offering an interpretable temporal structure for discovered communities in the dataset. Implementation of our method is available for download [64].

The goal in network state prediction (NSP) is to classify the global state (label) associated with features embedded in a graph. This graph structure encoding feature relationships is the key distinctive aspect of NSP compared to classical supervised learning. NSP arises in various applications: gene expression samples embedded in a protein-protein interaction (PPI) network, temporal snapshots of infrastructure or sensor networks, and fMRI coherence network samples from multiple subjects to name a few. Instances from these domains are typically “wide” (more features than samples), and thus, feature sub-selection is required for robust and generalizable prediction. How to best employ the network structure in order to learn succinct connected subgraphs encompassing the most discriminative features becomes a central challenge in NSP. Prior work employs connected subgraph sampling or graph smoothing within optimization frameworks, resulting in either large variance of quality or weak control over the connectivity of selected subgraphs. In this work we propose an optimization framework for discriminative subgraph learning (DSL) which simultaneously enforces (i) sparsity, (ii) connectivity and (iii) high discriminative power of the resulting subgraphs of features. Our optimization algorithm is a single-step solution for the NSP and the associated feature selection problem. It is rooted in the rich literature on maximal-margin optimization, spectral graph methods and sparse subspace self-representation. DSL simultaneously ensures solution interpretability and superior predictive power (up to 16% improvement in challenging instances compared to baselines), with execution times up to an hour for large instances.

Analysis of opinion dynamics in social networks plays an important role in today’s life. For predicting users’ political preference, it is particularly important to be able to analyze the dynamics of competing polar opinions, such as pro-Democrat vs. pro-Republican. While observing the evolution of polar opinions in a social network over time, can we tell when the network evolved abnormally? Furthermore, can we predict how the opinions of the users will change in the future? To answer such questions, it is insufficient to study individual user behavior, since opinions can spread beyond users’ ego-networks. Instead, we need to consider the opinion dynamics of all users simultaneously and capture the connection between the individuals’ behavior and the global evolution pattern of the social network. In this work, we introduce the Social Network Distance (SND)—a distance measure that quantifies the likelihood of evolution of one snapshot of a social network into another snapshot under a chosen model of polar opinion dynamics. SND has a rich semantics of a transportation problem, yet, is computable in time linear in the number of users and, as such, is applicable to large-scale online social networks. In our experiments with synthetic and Twitter data, we demonstrate the utility of our distance measure for anomalous event detection. It achieves a true positive rate of 0.83, twice as high as that of alternatives. The same predictions presented in precision-recall space show that SND retains perfect precision for recall up to 0.2. Its precision then decreases while maintaining more than 2-fold improvement over alternatives for recall up to 0.95. When used for opinion prediction in Twitter data, SND’s accuracy is 75.6%, which is 7.5% higher than that of the next best method.

Subgraph discovery in a data graph (finding subsets of vertices and edges satisfying a user-specified criteria) is an essential and general graph analytics operation with a wide spectrum of applications. We present Nuri, a general subgraph discovery system that allows users to succinctly specify subgraphs of interest and criteria for ranking them. Given such specifications, Nuri efficiently finds the k most relevant subgraphs. It prioritizes (i.e., expands earlier than others) subgraphs that are more likely to expand into the desired subgraphs (prioritized subgraph expansion) and proactively discards irrelevant subgraphs from which the desired subgraphs cannot be constructed (pruning). Nuri can also efficiently store and retrieve a large number of subgraphs on disk without being limited by the size of main memory. We demonstrate using both real and synthetic datasets that Nuri only on a single core outperforms the closest alternative distributed system running on 40 cores by more than 2 orders of magnitude for clique discovery and 1 order of magnitude for subgraph isomorphism and pattern mining.

Communities are essential building blocks of complex networks enjoying significant research attention in terms of modeling and detection algorithms. Common across models is the premise that node pairs that share communities are likely to interact more strongly. Moreover, in the most general setting a node may be a member of multiple communities, and thus, interact with more than one cohesive group of other nodes. If node interactions are observed over a long period and aggregated into a single static network, the communities may be hard to discern due to their in-network overlap. Alternatively, if interactions are observed over short time periods, the communities may be only partially observable. How can we detect communities at an appropriate temporal resolution that resonates with their natural periods of activity? We propose LARC, a general framework for joint learning of the overlapping community structure and the periods of activity of communities, directly from temporal interaction data. We formulate the problem as an optimization task coupling community fit and smooth temporal activation over time. To the best of our knowledge, the tensor version of LARC is the first tensor-based community detection method to introduce such smoothness constraints. We propose efficient algorithms for the problem, achieving a $2.6x$ quality improvement over all baselines for high temporal resolution datasets, and consistently detecting better-quality communities for different levels of data aggregation and varying community overlap. In addition, LARC elucidates interpretable temporal patterns of community activity corresponding to botnet attacks, transportation change points and public forum interaction trends, while being computationally practical---few minutes on large real datasets. Finally, LARC provides a comprehensive \em unsupervised parameter estimation methodology yielding high accuracy and rendering it easy-to-use for practitioners.

Reduction of end-to-end network delay is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks, and increased rate of packets in the case of communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such network design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search-space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. We consider the problem of network delay minimization via node upgrades. We show that the problem is NP-hard and prove strong inapproximability results about it (i.e., APX-hard) even for equal vertex delays. On the positive side, probabilistic approximations for a restricted version of the problem can be obtained. We propose a greedy heuristic to solve the general problem setting which has good quality in practice, but does not scale to very large instances. To enable scalability to real-world networks, we develop approximations for Greedy with probabilistic guarantees for every iteration, tailored to different models of delay distribution and network structures. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality. We evaluate our approaches on several real-world graphs from different genres. We achieve up to two orders of magnitude speed-up compared to alternatives from the literature on moderate size networks, and obtain high-quality results in minutes on large datasets while competitors from the literature require more than four hours.

Modeling and predicting people's opinions plays an important role in today's life. For viral marketing and political strategy design, it is particularly important to be able to analyze competing opinions, such as pro-Democrat vs. pro-Republican. While observing the evolution of polar opinions in a social network over time, can we tell when the network "behaved"' abnormally? Furthermore, can we predict how the opinions of individual users will change in the future? To answer such questions, it is insufficient to study individual user behavior, since opinions spread beyond users' ego-networks. Instead, we need to consider the opinion dynamics of all users simultaneously. In this work, we introduce the Social Network Distance (SND)-a distance measure that quantifies the likelihood of evolution of one snapshot of a social network into another snapshot under a chosen opinion dynamics model. SND has a rich semantics of a transportation problem, yet, is computable in pseudo-linear time, thereby, being applicable to large-scale social networks analysis. We demonstrate the effectiveness of SND in experiments with Twitter data.

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.

Reduction of end-to-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NP-hard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.

Many real-world complex systems can be modeled as dynamic networks with real-valued vertex/edge attributes. Examples include users' opinions in social networks and average speeds in a road system. When managing these large dynamic networks, compressing attribute values becomes a key requirement, since it enables the answering of attribute-based queries regarding a node/edge or network region based on a compact representation of the data. To address this problem, we introduce a lossy network compression scheme called Slice Tree (ST), which partitions a network into smooth regions with respect to node/edge values and compresses each value as the average of its region. ST applies a compact representation for network partitions, called slices, that are defined as a center node and radius distance. We propose an importance sampling algorithm to efficiently prune the search space of candidate slices in the ST construction by biasing the sampling process towards the node values that most affect the compression error. The effectiveness of ST in terms of compression error, compression rate, and running time is demonstrated using synthetic and real datasets. ST scales to million-node instances and removes up to 87% of the error in attribute values with a 103compression ratio. We also illustrate how ST captures relevant phenomena in real networks, such as research collaboration patterns and traffic congestions.

Learning a succinct set of substructures that predicts global network properties plays a key role in understanding complex network data. Existing approaches address this problem by sampling the exponential space of all possible subnetworks to find ones of high prediction accuracy. In this paper, we develop a novel framework that avoids sampling by formulating the problem of predictive subnetwork learning as node selection, subject to network-constrained regularization. Our framework involves two steps: (i) subspace learning, and (ii) predictive substructures discovery with network regularization. The framework is developed based upon two mathematically sound techniques of spectral graph learning and gradient descent optimization, and we show that their solutions converge to a global optimum solution - a desired property that cannot be guaranteed by sampling approaches. Through experimental analysis on a number of real world datasets, we demonstrate the performance of our framework against state-of-the-art algorithms, not only based on prediction accuracy but also in terms of domain relevance of the discovered substructures.

Information propagation in social media depends not only on the static follower structure but also on the topic-specific user behavior. Hence novel models incorporating dynamic user behavior are needed. To this end, we propose a model for individual social media users, termed a genotype. The genotype is a per-topic summary of a user's interest, activity and susceptibility to adopt new information. We demonstrate that user genotypes remain invariant within a topic by adopting them for classification of new information spread in large-scale real networks. Furthermore, we extract topic-specific influence backbone structures based on information adoption and show that they differ significantly from the static follower network. When employed for influence prediction of new content spread, our genotype model and influence backbones enable more than 20% improvement, compared to purely structural features. We also demonstrate that knowledge of user genotypes and influence backbones allow for the design of effective strategies for latency minimization of topic-specific information spread.

The study of influence, persuasion, and user sentiment dynamics within online communities has recently emerged as a highly active area of research. In this paper, we focus on analyzing and modeling user sentiment dynamics within a real-world social media such as Twitter. Beyond text and connectivity, we are interested in exploring the level of topical user posting activity and its effect on sentiment change. We perform topic-wise analysis of tweeting behavior that reveals a strong relationship between users' activity acceleration and topic sentiment change. Inspired by this empirical observation, we develop a new generative and predictive model that extends classical neighborhood-based influence propagation with the notion of user activation. We fit the parameters of our model to a large, real-world Twitter dataset and evaluate its utility to predict future sentiment change. Our model outperforms significantly (1 order of magnitude in accuracy) existing alternatives in identifying the individuals who are most likely to change sentiment based on past information. When predicting the next sentiment of users who actually change their opinion (a relatively rare event), our model is twice more accurate than alternatives, while its overall network accuracy is 94% on average. We also study the effect of inactive users on consensus efficiency in the opinion dynamics process both analytically and in simulation within the context of our model.

Nearest neighbor proximity search in large graphs is an important analysis primitive with a variety of applications in graph data from different domains. We propose a novel proximity measure for weighted graphs called Effective Importance which incorporates multiple paths between nodes and captures the inherent structural clusters within a network. We develop effective bounds on the EI value using a modified small subnetwork around a query node, enabling scalable exact nearest neighbor (NN) search at query time. Our NN search does not require heavy offline analysis or holistic knowledge of the graph, making our method suitable for very large dynamically changing networks or composite network overlays.

Processes within real world networks evolve according to the underlying graph structure. A number of examples exists in diverse network genres: botnet communication growth, moving traffic jams [1], information foraging [2] in document networks (WWW and Wikipedia), and spread of viral memes or opinions in social networks. The network structure in all the above examples remains relatively fixed, while the shape, size and position of the affected network regions change gradually with time. Traffic jams grow, move, shrink and eventually disappear. Public attention shifts among current hot topics inducing a similar shift of highly accessed Wikipedia articles. Discovery of such smoothly evolving network processes has the potential to expose the intrinsic mechanisms of complex network dynamics, enable new data-driven models and improve network design. We introduce the novel problem of Mining smoothly evolving processes (MINESMOOTH) in networks with dynamic real-valued node/edge weights. We show that ensuring smooth transitions in the solution is NP-hard even on restricted network structures such as trees. We propose an efficient filtering based framework, called LEGATO. It achieves 3-7 times higher scores (i.e. larger and more significant processes) compared to alternatives on real networks, and above 80% accuracy in discovering realistic "embedded" processes in synthetic networks. In transportation networks, LEGATO discovers processes that conform to existing traffic jams models. Its results in Wikipedia reveal the temporal evolution of information seeking of Internet users.

How to spot and summarize anomalies in dynamic networks such as road networks, communication networks and social networks? An anomalous event, such as a traffic accident, a denial of service attack or a chemical spill, can affect several near-by edges and make them behave abnormally, over several consecutive time-ticks. We focus on spotting and summarizing such significant anomalous regions, spanning space (i.e. nearby edges), as well as time. Our first contribution is the problem formulation, namely finding all such Significant Anomalous Regions (SAR). The next contribution is the design of novel algorithms: an expensive, exhaustive algorithm, as well as an efficient approximation, called NETSPOT. Compared to the exhaustive algorithm, NETSPOT is up to one order of magnitude faster in real data, while achieving less than 4% average relative error rate. In synthetic datasets, it is more than 30 times faster and solves large problem instances that are otherwise infeasible. The final contribution is the validation on real data: we demonstrate the utility of NETSPOT for inferring accidents on road networks and detecting patterns of anomalous access to subnetworks of Wikipedia. We also study NETSPOT'S scalability in large social, transportation and synthetic evolving networks, spanning in total up to 50 million edges.

Anomaly detection in dynamic networks has a rich gamut of application domains, such as road networks, communication networks and water distribution networks. An anomalous event, such as a traffic accident, denial of service attack or a chemical spill, can cause a local shift from normal behavior in the network state that persists over an interval of time. Detecting such anomalous regions of network and time extent in large real-world networks is a challenging task. Existing anomaly detection techniques focus on either the time series associated with individual network edges or on global anomalies that affect the entire network. In order to detect anomalous regions, one needs to consider both the time and the affected network substructure jointly, which brings forth computational challenges due to the combinatorial nature of possible solutions.

Networks from different genres are not static entities, but exhibit dynamic behavior. The congestion level of links in transportation networks varies in time depending on the traffic. Similarly, social and communication links are employed at varying rates as information cascades unfold. In recent years there has been an increase of interest in modeling and mining dynamic networks. However, limited attention has been placed in high-scoring sub graph discovery in time-evolving networks. We define the problem of finding the highest-scoring temporal sub graph in a dynamic network, termed Heaviest Dynamic Sub graph (HDS). We show that HDS is NP-hard even with edge weights in {-1,1} and devise an efficient approach for large graph instances that evolve over long time periods. While a naive approach would enumerate all O(t^2) sub-intervals, our solution performs an effective pruning of the sub-interval space by considering O(t*log(t)) groups of sub-intervals and computing an aggregate of each group in logarithmic time. We also define a fast heuristic and a tight upper bound for approximating the static version of HDS, and use them for further pruning the sub-interval space and quickly verifying candidate sub-intervals. We perform an extensive experimental evaluation of our algorithm on transportation, communication and social media networks for discovering sub graphs that correspond to traffic congestions, communication overflow and localized social discussions. Our method is two orders of magnitude faster than a naive approach and scales well with network size and time length.