Domination problems in social networks

PhD Thesis


Wang, Guangyuan. 2014. Domination problems in social networks. PhD Thesis Doctor of Philosophy. University of Southern Queensland.
Title

Domination problems in social networks

TypePhD Thesis
Authors
AuthorWang, Guangyuan
SupervisorWang, Professor Hua
Institution of OriginUniversity of Southern Queensland
Qualification NameDoctor of Philosophy
Number of Pages118
Year2014
Abstract

The thesis focuses on domination problems in social networks. Domination problems are one of the classical types of problems in computer science. Domination problems are fundamental and widely studied problems in algorithms and complexity theory. They have been extensively studied and adopted in many real-life applications. In general, a set D of vertices of a simple (no loops or multiple edges), undirected graph G = (V,E) is called dominating if each vertex in V −D is adjacent to some vertex in D. The computational problem of computing a dominating set of minimum size is known as “the dominating set problem”. The dominating set problem is NP-hard in general graphs. A social network - the graph of relationships and interactions within a group of individuals - plays a fundamental role as a medium for the spread of information, ideas, and influence among its members.

In a social network, people, who have problems such as drinking, smoking and drug use related issues, can have both positive and negative impact on each other and a person can take and move among different roles since they are affected by their peers. As an example, positive impacts of intervention and education programs on a properly selected set of initial individuals can diffuse widely into society via various social contacts: face to face, phone calls, email, social networks and so on. Exploiting the relationships and influences among individuals in social networks might offer considerable benefit to both the economy and society.

In order to deal with social problems, the positive influence dominating set (PIDS) is a typical one to help people to alleviate these social problems. However, existing PIDS algorithms are usually greedy and finding approximation solutions that are inefficient for the growing social networks. By now these proposed algorithms can deal with social problems only in undirected social networks with uniform weight value. To overcome the shortcomings of the existing PIDS model, a novel domination model namely weight positive influence dominating set (WPIDS) is presented. A main contribution of the thesis is that the proposed WPIDS model can be applied in weighted directed social networks. It considers the direction and degree of users’ influence in social networks in which the PIDS model does not. The experimental results have revealed that the WPIDS model is more effective than the PIDS model.

At the same time, thanks to the publication of Dijkstra’s pioneering paper, a lot of self-stabilizing algorithms for computing minimal dominating sets have been proposed, such as the self-stabilizing algorithms for minimal single dominating sets and minimal k-dominating sets (MKDS). However, for the MKDS problem, so far there is no self-stabilizing algorithm that works in arbitrary graphs. The proposed algorithms for the MKDS either work for tree graphs or find a minimal 2-dominating set. So, in the thesis, for the MKDS problem, two self-stabilizing algorithms are presented that can operate on general graphs. For the weighted dominating set (WDS) problem, most of the proposed algorithms find approximation solutions to a WDS. For the non-uniform WDS problem, there is no self-stabilizing algorithm for the WDS. In the thesis, self-stabilizing algorithms for the minimal weighted dominating set (MWDS) and minimal positive influence dominating set (MPIDS) are presented when operating in any general network. The worst case convergence time of the two algorithms from any arbitrary initial state are also proved. Finally, in order to reduce cost in an education/intervention programme arising from the PIDS problem, two cooperative cost games about PIDS problem are constructed.

KeywordsSocial problems, Dominating set, Positive influence dominating set, Weighted positive influence dominating set, K-dominating set, Weighted dominating set, Self-stabilizing algorithm, Daemon, Cooperative cost games, Computing complexity
ANZSRC Field of Research 2020529999. Other psychology not elsewhere classified
Byline AffiliationsSchool of Agricultural, Computational and Environmental Sciences
Permalink -

https://research.usq.edu.au/item/q31vq/domination-problems-in-social-networks

Download files


Published Version
Wang_whole_2014.pdf
File access level: Anyone

  • 1805
    total views
  • 742
    total downloads
  • 1
    views this month
  • 1
    downloads this month

Export as

Related outputs

Positive Influence Dominating Set Games
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui, Zhang, Ji, Yi, Xun and Yong, Jianming. 2014. "Positive Influence Dominating Set Games." Hou, Jiang-Liang, Trappey, Amy J. C., Wu, Chien-Wei, Chang, Kuo-Hao, Liao, Chuing-Shou, Shen, Wei-Ming, Barthes, Jean-Paul and Luo, Jun-Zhou (ed.) 18th IEEE International Conference on Computer Supported Cooperative Work in Design (CSCWD 2014). Hsinchu, Taiwan 21 - 23 May 2014 United States. https://doi.org/10.1109/CSCWD.2014.6846890
Finding weighted positive influence dominating set to make impact to negatives: a study on online social networks in the new millennium
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui and Zhang, Ji. 2014. "Finding weighted positive influence dominating set to make impact to negatives: a study on online social networks in the new millennium." Kaur, Harleen and Tao, Xiaohui (ed.) ICTs and the millennium development goals: a United Nations perspective. New York, NY. United States. Springer. pp. 67-81
Minimising k-dominating set in arbitrary network graphs
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui, Zhang, Ji and Zhang, Jinhua. 2013. "Minimising k-dominating set in arbitrary network graphs." Motoda, Hiroshi, Wu, Zhaohui, Cao, Longbing, Zaiane, Osmar, Yao, Min and Wang, Wei (ed.) 9th International Conference on Advanced Data Mining and Applications (ADMA 2013). Hangzhou, China 14 - 16 Dec 2013 Heidelberg, Germany. Springer. https://doi.org/10.1007/978-3-642-53917-6_11
Finding a weighted positive influence dominating set in e-learning social networks
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui, Zhang, Ji and Zhu, Guohun. 2013. "Finding a weighted positive influence dominating set in e-learning social networks." International Journal of Computers and Technology. 10 (10), pp. 2136-2145.
A self-stabilizing algorithm for finding a minimal positive influence dominating set in social networks
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui and Zhang, Ji. 2013. "A self-stabilizing algorithm for finding a minimal positive influence dominating set in social networks." Wang, Hua and Zhang, Rui (ed.) 24th Australasian Database Conference (ADC 2013). Adelaide, Australia 29 Jan - 01 Feb 2013 Sydney, Australia.
A Self-Stabilizing Protocol for Minimal Weighted Dominating Sets in Arbitrary Networks
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui and Zhang, Ji. 2013. "A Self-Stabilizing Protocol for Minimal Weighted Dominating Sets in Arbitrary Networks." Shen, Weiming, Li, Weidong, Barthes, Jean-Paul, Luo, Junzhou, Zhu, Haibin, Yong, Jianming and Li, Xiaoping (ed.) IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD 2013). Whistler, Canada 27 - 29 Jun 2013 United States. https://doi.org/10.1109/CSCWD.2013.6581012
A self-stabilizing algorithm for finding a minimal K-dominating set in general networks
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui and Zhang, Ji. 2012. "A self-stabilizing algorithm for finding a minimal K-dominating set in general networks." Xiang, Yang, Pathan, Mukaddim, Tao, Xiaohui and Wan g, Hua (ed.) 3rd International Conference on Data and Knowledge Engineering (ICDKE 2012). Fujian, China 21 - 23 Nov 2012 Berlin, Germany. Springer. https://doi.org/10.1007/978-3-642-34679-8_8
Positive influence dominating set in e-learning social networks
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui and Zhang, Ji. 2011. "Positive influence dominating set in e-learning social networks." Leung, H., Popescu, E., Cao, Y., Lau, R. W. H. and Nejdl, W. (ed.) 10th International Conference on Web-Based Learning (ICWL 2011): Advances in Web-Based Learning. Hong Kong, China 08 - 10 Dec 2011 Berlin, Germany. https://doi.org/10.1007/978-3-642-25813-8_9