Keywords

5.1 Introduction

Information and communication technologies (ICTs) facilitate the creation, storage, management and dissemination of information by electronic means. This definition includes radio, television, telephone, fax, computer and the Internet. Four characteristics describe these modern ICTs: (1) Interactivity: for the first time ICTs are effective two-way communication technologies. (2) Permanent availability: the new ICTs are available 24 h a day. (3) Global reach: geographic distances hardly matter any more. (4) Reduced costs for many: relative costs of communication have shrunk to a fraction of previous values (Gerster and Zimmermann 2003). ICTs comprise a variety of tools and facilitate improvement in information management and dialogue between individuals, groups, communities, etc. Further, ICTs refer to the internet-based tools (the World Wide Web, online forums and e-publications) and non-internet services (direct modem-to-modem links and dial-in bulletin board systems). In sum, ICTs play a major role in a nations politics, economy, social and cultural development.

The eighth Millennium Development Goals (MDGs) are international development goals that were officially established following the Millennium Summit of the United Nations in 2000, following the adoption of the United Nations Millennium Declaration. All 189 United Nations member states and at least 23 international organizations have agreed to achieve these goals by the year 2015. The goals are: ending poverty and hunger, universal education, gender equality, child health, maternal health, combating HIV/AIDS, environmental sustainability, and global partnership (MDG 8) (http://en.wikipedia.org/wiki/Millennium 2013).

The MDGs are an attempt to directly address fundamental injustices and inequities that currently blight our planet. So what a role do ICTs play to achieve those millennium goals? ICTs can be used to more effectively tackle the MDGs through improved monitoring and surveillance systems on progress toward the MDGs, improving economic growth and reducing poverty, and more efficient and effective provision of basic social services. So ICTs are not foreign to the MDGs, on the contrary. They are an integral part of the Millennium Agenda as reflected in MDG 8, target 18, which calls on bringing access to ICTs for all.

In the new millennium, ICTs can provide new and innovative solutions to traditional development goals. They can not only increase the efficiency and efficacy of public processes but also radically change the way in which development assistance is provided. ICTs have changed people’s communication patterns and provided new ways of maintaining online social networks. For example, users on Wikipedia can vote for or against the nomination of others to adminship (Burke and Kraut 2008); users at Epinions, which is a popular product review online social network with a very active user community, are connected into a network of trust and distrust, which is then combined with review ratings to determine which reviews are most authoritative (Guha et al. 2004; Massa and Avesani 2005). Recently a number of papers have begun to investigate negative as well as positive influence in social networks (Leskovec et al. 2010; Wang et al. 2009, 2011a).

Regularly, individuals tend to be influenced by the opinions/behaviors of their relatives, friends and colleagues. For examples, children whose parents smoked are twice as likely to begin smoking between 13 and 21 (Hill et al. 2005), and peer pressure accounts for 65 % reasons for binge drinking, a major health issue, by children and adolescents (Standridge et al. 2004). Moreover, the tendency of an user to adopts a behavior increases together with the number of his neighbors following that behavior. Recently, Wang et al. (2009) introduced a variation of dominating set, called Positive Influence Dominating Set (PIDS), originated from the context of influence propagation in social networks. A PIDS of a graph is a subset of nodes in the graph that any node are dominated by at least half of its neighbors. However, the existing research for the PIDS problem does not take into consideration the attributes, directions and degrees of persons’ influence. For example, in an e-learning program we should consider the authorities’ effect such as tutors who have strong positive influence on other persons and they should be without interference from others. That is, the influence between a tutor and other students is one-way. So we introduce a new domination, named Weighted Positive Influence Dominating Set (WPIDS) to discuss the comprehensive properties of users in online social networks.

In this chapter, we focus on the online social networks in which the users’ relationships can be either positive (indicating relations such as friendship) or negative (indicating relations such as opposition or antagonism) in the new millennium. The research problem in this chapter is to discuss how to effectively utilize the properties of social networks to spread positive ideas and information within a group. In one of our published papers, we utilized the characters of the users in online social networks to study how to effectively utilize positive users to affect the whole users in the e-learning environment (Wang et al. 2011b). We designed a new WPIDS model in an e-learning social network and proposed two selection algorithms for finding a WPIDS.

5.2 Related Work

In the new millennium, ICTs in the world have achieved great success. ICTs are playing an increasing role in our society. From the local to the global level, ICTs have permeated all areas that pertain to socio-economic development, and are enabling the development of new skills, competitiveness and growth, particularly in developing nations. Online social networks have developed significantly in recent years due to the rapid development of ICTs. For example, online social networks sites like Facebook, MySpace are among the most popular sites on the Internet; online social networks have also raise special interest among commercial businesses, medical and pharmaceutical companies as a channel to influence the opinion of their customers (Guha et al. 2004; Massa and Avesani 2005); even police has utilize the information in online social network sites to track down crimes (Lauchs et al. 2012; Medina et al. 2012).

Recently, a number of papers have begun to investigate negative as well as positive relationships in online social networks. The reason is that to investigate the relationships and influences among individuals in social networks might offer considerable benefit to both the economy and society. Domingos and Richardson (2001) were the first ones to study the propagation of influence and the problem of identification of the most influential users in networks. They proposed the data mining to viral marketing and first considered the customer’s values which it may influence other customers to buy. Kempe et al. (2003; 2005) investigated the problem of maximizing the expected spread of an innovation or behavior within a social network based on the observation that individuals’ decisions to purchase a product or adopt an innovation are strongly influenced by recommendations from their friends and acquaintances. Leskovec et al. (2007) studied the influence propagation in a different perspective in which they aimed to find a set of nodes in networks to detect the spread of virus as soon as possible.

Among some research, finding a proper subset of most influential individual is formulated into a domination problem. For example, Eubank et al. (2004) proposed a greedy approximation algorithm and proved that the algorithm gives a 1 + O(1) approximation with a small constant in O(1) to the dominating set problem in a power-law graph. Zhu et al. (2010) studied a new type of dominating set which satisfies the property that for every node not in the domination set has at least half of its neighbors which are in the dominating set. They presented results regarding the complexity and approximation in general graphs. Wang et al. (2009) introduced a variation of dominating set, called PIDS, originated from the context of influence propagation in social networks. Wang et al. (2011a) also proved that finding a PIDS of minimum size is APX-hard and proposed a greedy algorithm with an approximation ratio of H(δ), where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network. Thai et al. (2011) provided tight hardness results and approximation algorithms for many existing domination problems, especially the PIDS problem and its variations.

Domination problems are all NP-hard in general graphs (Garey and Johnson 1979). More and more researchers move their attention to compute approximation solutions to domination problems (Eubank et al. 2004; Torkestani and Meybodi 2012; Wang et al. 2011a). Since finding a PIDS of minimum size is APX-hard (Wang et al. 2011a) [APX-hardness of PIDS means that if N P ≠ P, then PIDS has no PTAS (polynomial-time approximation scheme)], some greedy approximation algorithms have been proposed (Wang et al. 2009, 2011a), which are all limited to find approximate solutions to the PIDS problem in large social networks. However, Wang et al. did not consider the asymmetry of their relationship, and fail to address the direction and degree of influence between their relationship (Wang et al. 2009, 2011a). Another drawback in Wang et al. (2009, 2011a) is they overlook the key persons’ strong influence during the procedure. In this paper, we study a typical e-learning social network and explore how to utilize e-learning networks topology properties to help e-learners to improve their achievements. Our research focuses on these reasonable factors between their relationships and aims to find a novel dominating set to positively dominate other users. Our case study and analysis indicate the effectiveness of our method.

5.3 Motivation and Contribution

In Wang et al. (2009), the authors introduced the notion of PIDS and proposed a greedy approximation PIDS selection algorithm in 2009. Recall that D ⊆ V is a positive influence dominating set (PIDS) (Wang et al. 2009, 2011a) if any node i in V is dominated by at least \( \left[\frac{d(i)}{2}\right] \) nodes (that is, i has at least \( \left[\frac{d(i)}{2}\right] \) neighbors) in D where d(i) is the degree of node i. Note that there are two requirements for PIDS:

  1. (1)

    Every node not in D has at least half of its neighbors in D;

  2. (2)

    every node in D also has at least half of its neighbors in D.

Wang et al. (2009) revealed that approximately 60 % of the whole group under consideration needs to be selected into the PIDS to achieve the goal that every individual in the community has more positive neighbors than negative neighbors. If we consider some key factors, such as direction and degree of each person’s influence. The size of the solution for selecting a proper subset of the whole group might be smaller and the algorithm might be more effective and economical.

Fig. 5.1
figure 1

An example of PIDS graph model

Full size image

Following the key factors as we analyzed above, Fig. 5.1 is a proper example which illustrates the scenario as discussed above. In Fig. 5.1, Bob, Tom, Don and Ann are four equal e-learners in a small leaning group. Any three of them form a PIDS satisfying its definition [requirements (1) and (2)]. But if Bob is a tutor and has strong positive influence on others, only Bob can positively affect (dominate) others. In this paper we consider the degree and direction of each user’s influence, propose a novel WPIDS and develop two WPIDS selection algorithms.

The main idea of our research is as to how to effectively select positive e-learners to affect an individual in the network becomes a “positive” user if its total neighbors’ positive influence is no less than the negative influence. We give both theoretical justification and empirical verification for the two proposed WPIDS selection algorithms. Specifically, we prove that the feasibility of the two WPIDS selection algorithms by a theorem. The contributions of our work are as follows:

  • A new WPIDS model and two WPIDS selection algorithms have been presented. The model reasonably utilizes its online social network structure to help e-learning users to improve their achievements.

  • The effectiveness of two proposed WPIDS selection algorithms has been evaluated by a case study and the discussion.

  • The differences between WPIDS and PIDS models and the causes why our WPIDS model is better than the PIDS one model have been discussed.

5.4 Problem Definitions

In this section, we formulate the WPIDS problem arising from e-learning online social networks. We will use the following network model to illustrate an e-learning online social network in context of the improving achievement issue: A digraph G = (V, A, C, W) is used to represent the e-learning online social network. V is the set of nodes in which each node is a user in the e-learning systems. A is the set of arcs in which each direct arc represents the existence of a social connection/influence between the two endpoints. C is the compartment vector that saves the compartment of each node. The compartment of a node decides whether it has positive or negative influence on its outgoing neighbors. For example, for the improving e-learning users’ achievements problem, the compartment of each node is one of the followings: authority (tutor), excellent student, average student, or poor student. A node in the authority or excellent student compartment has positive influence and all nodes in any of the other two compartments have negative influence. W is a set of weight values corresponding to arcs belonging to A. Each arc’s value is decided by the frequency of the two persons’ interactions.

In this chapter, we assume that (1) if the total arcs weight of an individual’s incoming neighbors has positive impact on him, then the probability that this individual positively impact others in the social network is high. (2) education/intervention programs can convert a negative influential individual to a positive influential person. (3) there are some authority users (tutors) with no incoming arcs which means that they are positive users without others’ influence.

Our first assumption comes from an extensive body of evidence suggesting that one of the most powerful predictors of habitual behavior in individuals is whether an individual has friends who also engage in that behavior (Crandall et al. 2008; Larimer and Cronce 2007; Walters and Bennett 2000). Due to outside competition in terms of personality traits attained from peer influence, the more neighbors/friends exerting positive influence, an individual has, the more likely he is to impact others in a positive way. Our second assumption comes from the work in Crandall et al. (2008), Jaccard et al. (2005), and Standridge et al. (2004), where nearly every individual in the feedback intervention program showed an improving grade in studying. The third assumption comes from the fact that the tutors are authorities in the study program who can not be affected by other students’ negative influence. With the above three assumptions, the problem is equivalent to selecting a subset of the whole e-learners in the e-learning program such that other e-learners in the system has more positive influence than negative influence.

The formal definitions of the WPIDS problem are as follows.

Definition 1 (E-learner Social Network).

An E-learner Social Network is a weighted digraph G = (V, A, C, W). V is the set of nodes in which each node is a user in the system. A is the set of arcs between the vertices: A = { (u, v) | u, v ∈ V and the user u influences the user v}. C is the compartment vector that saves the compartment of each node. The compartment of a node decides whether it has positive or negative influence on its outgoing neighbors. W is a set of weight values corresponding to arcs belonging to A. The weight value W of an arc (u, v) is defined as:

  • w(u, v) ∈ [−1, 0), if the user u is a negative user;

  • w(u, v) ∈ [0, 1], if the user u is a positive user.

Definition 2 (WPIDS).

With the above e-learner social network model, the WPIDS of an e-learner online social network G is defined as finding a WPIDS P of V such that any node u ∈ V − P is positively dominated by P. That is,

$$ \forall u\in V-P,{\displaystyle \sum}_{v\in {N}^{-}(u)}w\left(u,v\right)\ge 0, $$

where \( {N}^{-}(u)=\left\{v\Big|\left(v,u\right)\in A\right\} \) is the incoming neighbor nodes of node u.

Fig. 5.2
figure 2

An example of WPIDS graph model with an authority

Full size image

Example 2.1.

An example of WPIDS is shown in Fig. 5.2. Let node v 2 represents an authority (tutor) and nodes v 1, v 3, v 4 represent non-positive students, and let \( w\left({v}_2,{v}_1\right)=w\left({v}_2,{v}_3\right)=w\left({v}_2,{v}_4\right)=0.7 \), other arcs weight values are − 0. 3. According to the definition of WPIDS, the total incoming arcs weight values of nodes v 1, v 3, v 4 are 0.1. So the subset P = { v 2} is a WPIDS which shows the key person’s influence.

The WPIDS problem is to find a so-called minimum WPIDS of G, which minimizes the total number of its vertices. Since the WPIDS problem is NP-hard, in this chapter, we propose two selection algorithms for the WPIDS problem and find approximation solutions to WPIDS in large online social networks.

5.5 WPIDS Selection Algorithm

In this section, we present one theorem and two WPIDS selection algorithms for the WPIDS problem formalized in the above section. To do so, we first define a function f as follows.

Definition 3.

Consider a weighted digraph G = (V, A, C, W) as an instance of WPIDS. For any vertex subset P ⊆ V, we define

$$ w\left({n}_P^{-}(v)\right)={\displaystyle \sum}_{u\in {n}_P^{-}(v)}w\left(u,v\right),\kern0.92em f(P)={\displaystyle \sum}_{v\in V-P} \min \left\{0,w\left({n}_P^{-}(v)\right)\right\}, $$

where \( {n}_P^{-}(v)=\left\{u\Big|\left(u,v\right)\in P\right\} \) denotes the incoming neighbors nodes of v in P.

The following theorem states important properties of the function f.

Theorem 1.

  1. (1)

    f(∅) = 0.

  2. (2)

    \( \forall v\in V-P,f(P)=0, \) if and only if P is a WPIDS of G.

  3. (3)

    If f(P) < 0, then there exists a vertex u ∈ V − P such that \( f\left(P\cup \left\{u\right\}\right)>f(P) \) .

Proof.

Note that \( {n}_{\varnothing}^{-}(v)=\varnothing \) for all v ∈ V. Therefore (1) holds.

For (2), we note that f(P) = 0 if and only if \( 0\le w\left({n}_P^{-}(v)\right) \) for every v ∈ V − P if only if P is a WPIDS.

To see (3), note that f(P) < 0 implies the existence of v ∈ V − P such that \( 0>w\left({n}_P^{-}(v)\right) \). Let u be an incoming neighbor of v which is not in P and select u into P, then \( f\left(P\cup \left\{u\right\}\right)={\displaystyle \sum_{v\in V} \min \left\{0,w\left({n}_P^{-}(v)\right)+w\left(u,v\right)\right\}>f(P)} \).

Theorem 1 is the theoretical analysis to conduct two greedy algorithms for the WPIDS problem formalized in the earlier section. This is very important for running the algorithms in practice.

We define and explain a few terms and definitions used in the description of our algorithms. Let a weighted digraph G = (V, A, C, W) be an instance of WPIDS. Each node of V can have either positive or negative impact on its neighbor nodes. The positive degree of a node v affects an outgoing neighbor node u is the positive weight value of v ′ s outgoing arc weight value w(u, v). The same holds for negative degree. The compartment C of a node decides whether the node is a positive or a negative node. For example, in the e-learning communist, a node in the tutor compartment is a positive node and a node in any other compartment is a negative node. Nodes that are selected into the WPIDS are marked as positive nodes. Thus a e-learning user u is a positive user if u is initially a positive node or u is selected into the WPIDS. A PIDS P of a graph G is a subset of nodes in G that any node u in G is dominated by at least \( \left[\frac{d(u)}{2}\right] \) positive nodes (that is, u has at least \( \left[\frac{d(u)}{2}\right] \) positive neighbors) in P where d(u) is the degree of node u. A WPIDS P of a graph G is a subset of nodes in G such that any node u in V − P is positively dominated by the positive nodes in P (that is, the total influence value of u ′ s incoming neighbors is no less than zero).

We simply explain the following heuristic methods to obtain the two WPIDS selection algorithm.

First we only need to consider the users (nodes) who are not positively dominated. It is easy to imagine that we can get a more “greedy” algorithm if we choose users (nodes) with the biggest outgoing negative influence as dominators into the positive dominating set because they can have more positive influence to others. And repeat this procedure until all persons (nodes) not in the PIDS are positively dominated by their incoming neighbors. The details of this algorithm are presented in Algorithm 1.

Considering the fact that the negative users (nodes) who have the highest accumulative weights from other neighbors’ influence are easy to be educated into positive users, we propose another algorithm. The main idea of WPIDS Selection Algorithm 2 is to choose the users (nodes) from the negative users group with the highest accumulative weights of incoming arcs into the PIDS according to the fact that these selected persons are easier to be educated into positive users. The only difference between these two selection algorithms is that Algorithm 1 is to choose persons with the biggest outgoing negative influence as dominators and Algorithm 2 is to choose persons who are easy to change positive users as dominators. The pseudo codes of these two WPIDS selection algorithms are described in Algorithms 1 and 2 respectively.

We list the complete pseudo codes of Algorithms 1 and 2 as follows.

Fig. 5.3
figure 3

An example of WPIDS selection algorithm graph model

Full size image

Example 4.1.

Figure 5.3 shows how to operate our two WPIDS selection algorithms. Figure 5.3 is almost the same as Fig. 5.2 except one more negative node v 5 and let \( w\left({v}_4,{v}_5\right)=w\left({v}_5,{v}_4\right)=-0.2 \). According to Algorithm 1, the nodes v 1 and v 3 have already been positively dominated by the node v 2. So we just consider the nodes v 4 and v 5. The node v 4 has the smallest total outgoing arcs weight value ( − 0. 8) and the node v 5 has total outgoing arcs weight values is − 0. 2, so the node v 4 is selected as a positive node. The arc weight w(v 4, v 5) becomes 0.2 which can positively dominate the node v 5. Consequently, the set {v 2, v 4} is a WPIDS which can positively dominate the whole nodes. According to Algorithm 2, The node v 4 has the biggest total ingoing arcs weight value ( − 0. 1) and the node v 5 has total ingoing arcs weight values is − 0. 2, so the node v 4 is selected as a positive node. The arc weight w(v 4, v 5) becomes 0.2 which can positively dominate the node v 5. The set {v 2, v 4} is a WPIDS.

5.6 Case Study

5.6.1 A Real-World Case

In this section we use a studying group (Fig. 5.4) to discuss the differences between WPIDS and PIDS selection algorithms. The studied case is depicted in Fig. 5.4. The scenario undergraduates are picked up from a computer science class,Footnote 1 where Bob is a tutor and other person are non-positive students in a small e-learning group. Ann is a quiet and introverted girl who has limited influence to others. In Fig. 5.4, the arcs weight values are the same as in Fig. 5.3 and Ann has − 0. 1 influence value to Don. According to our WPIDS definition, Bob and Kris are the WPIDS. If we get rid of the arc’s weights and direction Don and Kris are the PIDS according to its definition (Wang et al. 2009). The obvious difference between these two solutions is that the solution to WPIDS select Bob as one of the dominators and considers the fact Bob is a tutor which should be as a key person and plays an important role in the program. But the solution to PIDS does not. Another difference is our graph model is directed that means the influence of relationship between users is different. But the influence between users in PIDS model is uniform (Wang et al. 2009).

Fig. 5.4
figure 4

A case study of WPIDS selection algorithm group model

Full size image

5.6.2 Discussions

So from the case study of Fig. 5.4, we can see that the WPIDS in our model has some different real meanings from the PIDS model in paper (Wang et al. 2009). One of our improvements is that we consider the reasonable partition of persons who attended the program. Either in e-learning programs or drinking (smoking, drug) intervention strategies and programs we should consider the authorities’ effect such as tutors or correctional officers who have strong positive influence on other persons and they should be without interference from others. In other words, they are the key persons who play important roles during the program. For example, in the above case study Bob is a tutor which should be as a key person and a positive dominator. But the solution to PIDS does not select Bob as a dominator. Due to Ann’s special situation, Kris should be selected into WPIDS to positively influence Ann instead of other persons. This solution shows the importance of influence’s directions. For example, the influence of relationship between tutors and students can be considered one-way. The fact is that the degree of influence between two persons is different and should be considered. Besides, our definition of the dominating problem is more reasonable than that of PIDS since one person’s neighbors’ degree of influence is the decisive factor instead of the number of his/her neighbors. So in order to positively dominate the whole group we can strengthen influence on the key persons instead of increasing the number of positive persons. So through these discussion we can draw a conclusion our WPIDS model is more reasonable and effective than PIDS model in paper (Wang et al. 2009).

5.7 Conclusions and Future Work

In this chapter, we introduced online Social Networks which are developing rapidly by the impact of ICTs in the New Millennium. We studied the users’ relationship in online social networks, focusing on the positive or negative influence between users in e-learning system. We have proposed a new domination named WPIDS and developed two WPIDS selection algorithm to evaluate the effect of educating a subset of the entire target group susceptible to a social problem. Our idea is how to utilize online social network as a medium to improve users’ achievements. The case study has revealed that the WPIDS model and algorithm are more effective than those of PIDS (Wang et al. 2009). Since the tutors play important roles in the e-learning community the size of WPIDS is smaller than that of PIDS in a large online social networks.

For the further research work of the WPIDS problem, we are interested in comparing our WPIDS algorithm with the PIDS algorithm in empirical experiments in future work. Since it is very important to specify the reasonable arc weight values of the e-learning users’ influence, how to quantify the degree of the users’ influence in real-life world is a challenging task.