划分图上的正影响数(英文)

Positive Influencing Number of Partitioned Graphs

一个社会网络中通常包括具有正面影响和负面影响的两类人员,为了研究这个社会网络中人们之间相互影响的某些规律,引入了一个新的概念.用划分图G=(V,E),V=V+∪V^-表示这样的一个社会网络,其中V^+和V^-分别表示正面人员的集合和负面人员的集合.图G的一个点子集D(?)V^-被称为G的一个正影响集,若G的每个点的至少一半的邻点在D∪V^+中.G的所有正影响集的最小基数称为G的正影响数.给出G的正影响数的几个下界并证明了这些界是紧的.此外,还证明了求正影响数问题在二部图和弦图上都是NP-完全的.

In this paper,a concept is introduced in order to model a class of problems in social networks.A social network consisting of positive and negative influential individuals is represented as a partitioned graph G =(V,E) with vertex set partition V =V+ ∪ V-.A subset D (∈) V- is called a positive influencing set if every vertex of G has in D ∪ V+ at least half of its neighbors.The positive influencing number of G is the minimum cardinality of a positive influencing set.In the present paper,we show some sharp lower bounds for this parameter,and prove that this problem is NP-complete for partitioned bipartite graphs and partitioned chordal graphs,respectively.