An Approximation Algorithm for the Influential Nodes Selection Problem in Social Network∗

JI Gui-lin,HUANG Xiao-hui

(College of Mathematics and System Sciences,Xinjiang University,Urumqi,Xinjiang 830046,China)

Abstract: In this paper,we study the problem of selecting a minimum set S of influential nodes in a social network G such that every node in V(G)−S has at least half of its neighbors in S.An approximation algorithm is given with performance ratio αl(∆+1)/δ+1,where δ and ∆ are the minimum and the maximum degree of G,respectively,and αl is the local independence number indicating how many independent nodes can be distributed in a local area.

Key words:Social network;influential node selection;approximation algorithm,independent set

0 Introduction

In a social network,we are to send an information to the whole network.To save energy and resources,only a fraction of the individuals are chosen as the initial targets.Then they further forward the information to their acquaintances.We want to choose the initial target set as small as possible.Notice that acknowledging an information is different from receiving it.One receives an information but he can refuse to acknowledge it.an individual acknowledges the information if at least half of its acquaintances already know it.As to the people in the initial target set,who are called influential nodes,we assume that they acknowledge the information immediately.

A problem is to find a minimum vertex setSof a graphG=(V,E)such that each vertexv∈VShas at leastneighbors inS,whered(v)=dG(v)is the degree of vertexvinG.we abbreviate the problem as INS.

In this paper,we propose an approximation algorithm for INS using a new parameter which we call as local independence number.For a vertexu∈V,we useN(u)=NG(u)to denote the set of neighbors ofuinG.An independent set(IS)of a graphGis a vertex subsetI⊆Vsuch that there is no edge between any two vertices ofI.Given an independent setIofG,we define

as the local independence number of vertexuwith respect toI.For a graphG,we defineas the local independence number of graphG,where the maximum is taken over all the verticesuand all the independent setsIofG.

In this paper,we propose an approximation algorithm and show that it has approximation ratio αl(∆ +1)/δ+1,where δ and ∆ are the minimum and the maximum degree ofG,respectively.

Some related works are as follows:Domingos and Richardson[1,2]were the first to study the influential node selection problem in social networks,Kempe,Kleinberg and Tardos[3,4]proposed a probabilistic model called Influence Maximization Problem,in which the goal is to select a set of influential nodes not more than a constantksuch that the expected number of nodes which are eventually influenced is maximum.Their work was further generalized by Mossel and Roch[5]to include a large amount of situations.Thet-Latency Bounded Fast Information Propagation Problem(t-LBFIP)proposed in[6]asks for a minimum initial target set such that the information can be acknowledged by everyone in time not later thant-slots,The NP-hardness oft-LBFIP was proved and a greedy algorithm with approximation ratiowas given in[7],whereis the Harmonic function.

For terminologies not given here,we refer to[8].

1 The Algorithm and Its Analysis

LetSbe a subset of vertices.A vertexvis said to have met its covering requirement if eitherv∈Sorvhas at leastd(v)/2 neighbors inS.An independent setIis said to be a maximal independent set(MIS)if for any vertexv∈VI,the setI∪{v}is no longer independent.The idea of the algorithm is to iteratively adding an MIS to the selected set until every vertex has met its covering requirement.The algorithm is described in Algorithm 1.For a vertex subsetR⊆V,we useG[R]to denote the subgraph ofGinduced byR.

In order to analyze the approximation ratio,we study the relation between the size of MIS and the optimal value.

Lemma 1LetS∗be an optimal solution to the INS ofG,Ibe an independent set ofG.Then

ProofDenote byX=IS∗,Y=S∗I.Construct a bipartite graphHwith bipartition(X,Y).A vertexx∈Xis adjacent with a vertexy∈YinHif and only ifx,yare adjacent inG.Then for any vertexx∈X,dH(x)=|NG(x)∩Y|,and for any vertexy∈Y,dH(y)=|NG(y)∩X|.Clearly,

Being a subset of an independent set,Xis also an independent set.Combining this with the fact that every vertexx∈VS∗has at leastneighbors inS∗,we see that every vertexx∈Xhas at leastneighbors inY.Hence,

On the other hand,we see form the definition of αthat

Hence

The inequality of the lemma follows immediately.

Theorem 1Algorithm 1 has approximation ratio αl(∆+1)/δ+1.

ProofSuppose Algorithm 1 runstiterations and the final output isS=I1∪I2∪...∪It,whereIiis the MIS found in theithiteration.LetS∗be an optimal solution.

For eachi∈ {1,2,...,t},denoteRi−1the setRafter the(i− 1)thiteration of the algorithm.Notice thatG[Ri−1]is a subgraph ofG−I1∪I2∪...∪Ii−1(it might be a proper subgraph since those vertices whose covering requirements have been met are deleted).Since eachIjis an maximal independent set,we see that each vertexu∈Ri−1−Iiis adjacent with everyIjforj=1,2,...,i,and thusuhas at leastineighbors inI1∪I2∪...∪Ii.It follows thatBy Lemma 1,holds for any 1 ≤i≤t.Hence we have

Then,

The approximation ratio follows.