Positive Influencing Number of Partitioned Graphs
Zhao Weiliang, Zhao Yan-cai · 2012
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.