Evolving Networks: Models, Analysis & Validations

Evolution is manifested to be a common property of many realistic networks, which are observed to exhibit both the arrival of new nodes and the creation of new edges. There are three major research topics in evolving networks: observation, modeling and application.

Our research mainly focuses on observing and modeling evolving networks and studying its impact on the performance of some applications, for example, information diffusion. We try to answer several challenging questions: (1) What are the distinctive features exhibited in evolving network? (2) How to quantitively model those features? (3) What’s the impact of the features on network applications?

We empirically characterize the properties of evolving networks with hybrid interactions based on several datasets and results show that the networks exhibit some basic properties such as densification and shrinking diameter, as well as a distinctive one that degrees of a node in multi-layer networks are positively correlated. Based on those observations, we develop a novel model named Evolving K-Graph that can reproduce the above features with superiorities of mathematical tractability and efficient implementation.(see our MobiHoc’17 for more details)

In addition, we demonstrate that the delivery accuracy of information diffusion can be improved with the network evolution, which can even achieve a perfect state where those who receive the data are exactly the ones that are interested in it.

Information Diffusion / Cascades

One major feature of social networks is the dissemination of information. To measure such a property, we mainly focus on the diffusion of a piece of information in the whole networks which starts from a single user, which is closely related to the giant connected components.

We are interested in two aspects: (1) on what condition a single node can spread an item of information to a positive fraction of individuals in the interdependent networks? (2) how does clustering affect the global cascading and information diffusion?

For the problem of information diffusion, there is a commonly studied model called the SIR epidemic model, which requires an individual is either susceptible (S), or infectious (I), or recovered (R). Using the generating functions formalism, the intra-layer diffusion is analyzed with bond percolation theory, while the interlayer diffusion is compared to the cascading failure theory. Besides, we have further studied on the impact of clustering on the performance of information diffusion along with network de-anonymization.A related work can be referred to our AAAI’16 paper.

Influence Maximization in Social Networks

In viral marketing, social networks are becoming important platforms since users are more willing to accept advertisements propagated from their friends. For triggering wide diffusion of products or ideas under limited budgets, the Influence Maximization (IM) problem which focuses on selecting most influential seed users is naturally attached great importance.

We focus on studying three aspects of IM problem: (1) effectively promoting points of interests which can be formalized as a location-aware IM problem; (2) how to reasonably assign budgets for seed users with the friendship paradox phenomenon in social networks; (3) adaptively select seed users in the dynamical evolution networks which follows the preferential attachment rule.

We propose to form the users sharing similar activity areas into groups and then design the location-aware IM problem on group-level with the objective being selecting K most influential groups (see our KDD’17 submission for more details).And targeting on groups can propagate locations more effectively and efficiently. The probability that users become seeds in viral marketing increase with the discounts they received, and not all influential users are available for marketers while they can be influenced by their friends. We thus further study the two-stage discounts allocation method considering that friends of initial available users are more influential than them (friendship paradox). In evolution social networks, there are always new users to join the network and prefer to establish connections with those have high degrees. We then design the adaptive seeding method considering the evolution of networks based on the multi-armed bandits,in which we consider the influence of seed users on both the existing users and those joining in the future.

Connectivity Determination in Uncertain Graphs

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links.

The fundamental challenge we want to address is to determine the source destination connectivity in uncertain graphs that takes into consideration the uncertainty in networks.

We explore the problem of source destination connectivity in uncertain graphs ( INFOCOM’17, ToN’16, MobiHoc’14) We first precisely define the problem and formally characterize the computational hardness of the problem through two NP-hardness results. We subsequently designed an exact algorithm to gain insight of the problem. Then we propose two more efficient approximation algorithms with provable performance guarantee.

User Privacy Protection in Social Networks

Massive generation of publicly available social network data has made re-identifying anonymized published social networks through correlated cross-domain auxiliary networks a crucial privacy driven issue.

The key problem we want to investigate is to de-anonymize users in the anonymized networks by constructing a mapping from the auxiliary networks when the networks are community-structured.

We start by a succinct and practical modeling of community-based published and auxiliary social networks (See our Arxiv Paper for more details) . We then propose a cost function based on MAP estimate, through minimizing which we can almost surely recover the true mapping. Subsequently, we explore the optimization problem induced by the cost function from an algorithmic perspective. We design an approximation algorithm with provable approximation guarantee and an efficient heuristic that can yield the optimal solution under certain conditions.

Network Robustness&Controllability

It was found that the robustness of network controllability is closely related to the presence of the core in the network. The core of a network shows an interesting interplay between the structural and dynamical properties on network controllability.

We mainly focused on (1) the conditions for the emergence of the core, (2) the fraction of core users in the networks, and further studied (3) the impact of clustering on the performance of the robustness of network controllability.

Based on Erdos-Renyi Model, we improved this measurement to interdependent networks and proposed an Alternating GLR Procedure to get the core of the fully interdependent networks(see our MobiHoc’17 paper for more details). Then we utilize a more general static scale-free network model to study the impact of clustering. And we find that the result is quite different from that on single networks, where the fraction of core nodes undergoes a second order phase transition. For next step we are going to study the partially interdependent networks and the case of one-to-many relationship in interdependent networks.