Domination problems in social networks

Domination problems in social networks

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.