2010 FindingEffectorsinSocialNetwork

• (Lappas et al., 2010) ⇒ Theodoros Lappas, Evimaria Terzi, Dimitrios Gunopulos, and Heikki Mannila. (2010). “Finding Effectors in Social Networks.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835937

Subject Headings:

Notes

• Categories and Subject Descriptors: G.2.2 Discrete Mathematics: Graph Theory oryU-Graph algorithms; H.2.8 Database Management: Database applications — Data Mining.
• General Terms: Algorithms, Experimentation, Theory

Cited By

• http://scholar.google.com/scholar?q=%22Finding+effectors+in+social+networks%22+2010
• http://portal.acm.org/citation.cfm?id=1835937&preflayout=flat#citedby

Quotes

Author Keywords

Social Networks, information propagation, graph algorithms.

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 [math]\displaystyle{ k }[/math] active nodes that best explain the observed activation state, under a given information-propagation model. We call these nodes effectors. We formally define the [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ k }[/math]-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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 FindingEffectorsinSocialNetwork	Heikki Mannila Dimitrios Gunopulos Theodoros Lappas Evimaria Terzi			Finding Effectors in Social Networks		KDD-2010 Proceedings	http://cs-people.bu.edu/evimaria/papers/rp262b-lappas.pdf	10.1145/1835804.1835937		2010