Dynamic network analysis

Dynamic network analysis (DNA) is an emergent scientific field that brings together traditional social network analysis (SNA), link analysis (LA), social simulation and multi-agent systems (MAS) within network science and network theory. Dynamic networks are a function of time (modeled as a subset of the real numbers) to a set of graphs; for each time point there is a graph. This is akin to the definition of dynamical systems, in which the function is from time to an ambient space, where instead of ambient space time is translated to relationships between pairs of vertices. Overview There are two aspects of this field. The first is the statistical analysis of DNA data. The second is the utilization of simulation to address issues of network dynamics. DNA networks vary from traditional social networks in that they are larger, dynamic, multi-mode, multi-plex networks, and may contain varying levels of uncertainty. The main difference of DNA to SNA is that DNA takes interacti

Un modèle factoriel dynamique pour séries temporelles

Andrei Zenide

This work deals with factorial models for multiple time series. Its core content puts it at the interface between statistics and finance. After a brief description of the historical link between the two sciences, it reviews the literature on factorial models that are close to the model introduced in this work called The dynamical factor analysis model for time series. This model makes the hypothesis that the observed time series are influenced by a common factor, difficult to define and impossible to measure. No a priori structure is put on the factor, at each point time the value of the factor is considered as a new parameter that has to be estimated. As a consequence of this fact, the number of parameters is large and it is not possible to provide the usual asimptotic properties of the estimations by letting the number of periods tend to infi- nity. Asymptotic results in our context have been obtained by increasing the number of time series. The model makes the hypothesis that there is a linear dependence between the time series and the factor with coefficients, that are not constant over time, but rather follow a smooth random walk. This mean that the linear structure of the model is evolving slowly from a period to another. All the information which is not contained in the factor and the coefficients is considered as white noise. Using the normal distribution makes the estimation more easy and opens a toolbox of statistical methods that have been developed for this kind of data. The model is a part of the family of state space models and the Kalman filter is an essential ingredient of our estimator. The effort was concentrated on the elaboration of the structure of the model. Its complexity was constrained by the difficulty of estimation. The final shape of the model does not allow an analytical solution of the optimization problem introduced by the maximum likelihood estimation of the parameters. Numerical solutions have been found and compared with the parameters for simulated data. Some others models have been developed as simpler versions of the dynamical factor model for time series. The case where the factor can be observed has been studied and a new method for the estimation has been provided and compared with the existing methods. A second study considers a latent factor model without noise. Two methods for the estimation of the factor have been provided. The last chapter contains a detailed description of the main statistical tools used during this work. The links with the previous chapters are highlighted followed by comments.

EPFL2004

Privacy and Dynamics of Social Networks

Pedram Pedarsani

Over the past decade, investigations in different fields have focused on studying and understanding real networks, ranging from biological to social to technological. These networks, called complex networks, exhibit common topological features, such as a heavy-tailed degree distribution and the small world effect. In this thesis we address two interesting aspects of complex, and more specifically, social networks: (1) users’ privacy, and the vulnerability of a network to user identification, and (2) dynamics, or the evolution of the network over time. For this purpose, we base our contributions on a central tool in the study of graphs and complex networks: graph sampling. We conjecture that each observed network can be treated as a sample from an underlying network. Using this, a sampling process can be viewed as a way to observe dynamic networks, and to model the similarity of two correlated graphs by assuming that the graphs are samples from an underlying generator graph. We take the thesis in two directions. For the first, we focus on the privacy problem in social networks. There have been hot debates on the extent to which the release of anonymized information to the public can leak personally identifiable information (PII). Recent works have shown methods that are able to infer true user identities, under certain conditions and by relying on side information. Our approach to this problem relies on the graph structure, where we investigate the feasibility of de-anonymizing an unlabeled social network by using the structural similarity to an auxiliary network. We propose a model where the two partially overlapping networks of interest are considered samples of an underlying graph. Using such a model, first, we propose a theoretical framework for the de-anonymization problem, we obtain minimal conditions under which de-anonymization is feasible, and we establish a threshold on the similarity of the two networks above which anonymity could be lost. Then, we propose a novel algorithm based on a Bayesian framework, which is capable of matching two graphs of thousands of nodes - with no side information other than network structures. Our method has several potential applications, e.g., inferring user identities in an anonymized network by using a similar public network, cross-referencing dictionaries of different languages, correlating data from different domains, etc. We also introduce a novel privacy-preserving mechanism for social recommender systems, where users can receive accurate recommendations while hiding their profiles from an untrusted recommender server. For the second direction of this work, we focus on models for network growth, more specifically where the number of edges grows faster than the number of nodes, a property known as densification. The densification phenomenon has been recently observed in various real networks, and we argue that it can be explained simply through the way we observe (sample) networks. We introduce a process of sampling the edges of a fixed graph, which results in the super-linear growth of edges versus nodes, and show that densification arises if and only if the graph has a power-law degree distribution.

EPFL2013

Privacy and Dynamics of Social Networks

Pedram Pedarsani

EPFL2013

Un modèle factoriel dynamique pour séries temporelles

Andrei Zenide

EPFL2004

Dynamic Factor Analysis

Un modèle factoriel dynamique pour séries temporelles

Privacy and Dynamics of Social Networks

Privacy and Dynamics of Social Networks

Un modèle factoriel dynamique pour séries temporelles

Dynamic Factor Analysis