Name
Abstract | ||
|---|---|---|
Assume a network (V,E) where a subset of the nodes in V are active. We consider the problem of selecting a set of k active nodes that best explain the observed activation state, under a given information-propagation model. We call these nodes effectors. We formally define the k-Effectors problem and study its complexity for different types of graphs. We show that for arbitrary graphs the problem is not only NP-hard to solve optimally, but also NP-hard to approximate. We also show that, for some special cases, the problem can be solved optimally in polynomial time using a dynamic-programming algorithm. To the best of our knowledge, this is the first work to consider the k-Effectors problem in networks. We experimentally evaluate our algorithms using the DBLP co-authorship graph, where we search for effectors of topics that appear in research papers. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1835804.1835937 | KDD |
Keywords | Field | DocType |
information propagation,k-effectors problem,social networks,arbitrary graph,dblp co-authorship graph,different type,information-propagation model,social network,graph algorithms,k active node,observed activation state,dynamic-programming algorithm,polynomial time,nodes effectors,dynamic programming algorithm | Graph algorithms,Graph,Social network,Computer science,Artificial intelligence,Information propagation,Time complexity,Machine learning | Conference |
Citations | PageRank | References |
93 | 4.14 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Theodoros Lappas | 1 | 670 | 36.00 |
| Evimaria Terzi | 2 | 1580 | 83.54 |
| Dimitrios Gunopulos | 3 | 7171 | 715.85 |
| Heikki Mannila | 4 | 6595 | 1495.69 |