A study of social networks: an Lp norm relaxation approach
2013-04
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
A study of social networks: an Lp norm relaxation approach
Authors
Published Date
2013-04
Publisher
Type
Thesis or Dissertation
Abstract
In this thesis, an Influence Maximization problem in Social Network under the Deterministic Linear Threshold model and Discovering Efficient Sets of Key Players in Directed Weighted Social Networks are considered. In the first problem, the objective is to minimize the number of eventually negatively opinionated nodes in the network in a dynamic setting. The main ingredient of the new approach is the application of the sparse optimization technique. In the presence of inequality constraints and nonlinear relationships, the standard convex relaxation method of the L1 relaxation does not perform well in this context. Therefore we propose to apply the Lp relaxation where 0<p<1. The resulting optimization model is therefore non-convex. By means of an interior point method, the model can be solved efficiently and stably, typically yielding robust and sparse solutions in our numerical experiments with the simulated data. In the latter problem, the objective is to find the seed sets to maximize the influence subject to the constraint of budget only in the first stage. There has been a lot of different approaches to this problem. However, those approaches are all mostly specifically based on graph theory. In the era of big data, much information may be known such as the initial state and the threshold of the individuals in the social network by data mining and statistics. Algorithm design taking into account such factors considered is a new challenge. This thesis shows that the Lp norm relaxation is a promising approach to tackle this problem.
Description
University of Minnesota M.S. thesis. April 2013. Major: Industrial and Systems Engineering. Advisor: Shuzhong Zhang. 1 computer file (PDF); xiii, 54 pages.
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Xu, Rupei. (2013). A study of social networks: an Lp norm relaxation approach. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/157532.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.