Influence on information networks and sparse representation of metric spaces: y Li Ning.

Abstract

As the social networking applications become popular and have attracted more and more attention, it becomes possible (or easier) to mine information networks of a large group of people, for instance the spread of viruses, products and innovations. Researchers are also benefited from these sources, as they help to study further about the human behaviors in a social networking environment. In this thesis, we study how the opinions cascade via social links and also the sparse representation of large data sets caused by the fast growing information networks.

Consider an instance of advertising products on an information network, where the objective for an advertiser is to choose a set of initially active nodes, subject to some budget constraints such that the expected number of active nodes over time is maximized. In this work, the non-progressive case where active nodes could become inactive in subsequent time steps, was considered. This setting is interesting, for people have no reason to keep using a product forever, especially when a majority of his neighbors have given it up. Another setting is the users' susceptibilities to the new behavior won't change once they are chosen initially. This is di_erent from the previous works, and we think it is also interesting.

Our main result is that with a specified budget, an advertiser can achieve 1/2 -approximation on maximizing the number of active nodes over a certain period of time, and (1 - 1/e)-approximation in expectation with a randomized algorithm.

In our model, users' opinions are updated according to a weighted averaging scheme, which usually leads to the consensus. When this happens, the expected influence over a long time period is dominated by the consensus value. Hence, it is interesting to study when and how the consensus will be achieved. We study the convergence time required to achieve consensus. In particular, we considered the case when the underlying network is dynamic, and gave conclusions for different averaging models. Both our analysis and experiments show that dynamic networks exhibit fast convergence behavior, even under very mild connectivity assumptions.

In this work, we also studied how to maintain the pairwise distances for a large group of users, when the distances form a doubling metric space. Motivated by Elkin and Solomon's construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n) ． w(MST)), we offer a simple alternative construction that is very intuitive and is based on the standard technique of net tree with cross edges. Indeed, our approach can be readily applied to our previous construction of k-fault tolerant spanners (ICALP 2012) to achieve k-fault tolerance, maximum degree O(K^2), hop-diameter O(log n) and lightness O(K^3 log n).