File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Influence on information networks and sparse representation of metric spaces: y Li Ning.
Title  Influence on information networks and sparse representation of metric spaces: y Li Ning. 

Authors  
Issue Date  2013 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Ning, L. [宁立]. (2013). Influence on information networks and sparse representation of metric spaces / y Li Ning. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5066215 
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 nonprogressive 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, hopdiameter 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 kfault tolerant spanners (ICALP 2012) to achieve kfault tolerance, maximum degree O(K^2), hopdiameter O(log n) and lightness O(K^3 log n). 
Degree  Doctor of Philosophy 
Subject  Information networks. Sparse matrices. 
Dept/Program  Computer Science 
Persistent Identifier  http://hdl.handle.net/10722/191190 
HKU Library Item ID  b5066215 
DC Field  Value  Language 

dc.contributor.author  Ning, Li   
dc.contributor.author  宁立   
dc.date.accessioned  20130930T15:52:25Z   
dc.date.available  20130930T15:52:25Z   
dc.date.issued  2013   
dc.identifier.citation  Ning, L. [宁立]. (2013). Influence on information networks and sparse representation of metric spaces / y Li Ning. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5066215   
dc.identifier.uri  http://hdl.handle.net/10722/191190   
dc.description.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 nonprogressive 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, hopdiameter 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 kfault tolerant spanners (ICALP 2012) to achieve kfault tolerance, maximum degree O(K^2), hopdiameter O(log n) and lightness O(K^3 log n).   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  Creative Commons: AttributionNonCommerical 3.0 Hong Kong License   
dc.source.uri  http://hub.hku.hk/bib/B50662156   
dc.subject.lcsh  Information networks.   
dc.subject.lcsh  Sparse matrices.   
dc.title  Influence on information networks and sparse representation of metric spaces: y Li Ning.   
dc.type  PG_Thesis   
dc.identifier.hkul  b5066215   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Computer Science   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b5066215   
dc.date.hkucongregation  2013   