nach oben

Social Network Analysis and Mining

Erschienen in:

01.06.2013 | Original Article

On tractable cases of Target Set Selection

verfasst von: André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller

Erschienen in: Social Network Analysis and Mining | Ausgabe 2/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size “target set” such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are active. Then, a vertex becomes active if the number of its active neighbors exceeds its threshold, and so on. TSS models the spread of information, infections, and influence in networks. Complementing results on its polynomial-time approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters “diameter”, “cluster editing number”, “vertex cover number”, and “feedback edge set number” of the underlying graph on the problem’s computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter “size of the target set”. TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter “treewidth”. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter “cluster editing number”, yielding tractability for certain dense networks.

Vorheriger Artikel A social network analysis and mining methodology for the monitoring of specific domains in the blogosphere

Nächster Artikel Web sessions clustering using hybrid sequence alignment measure (HSAM)

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Informally speaking, W[1]-hardness means that there is no hope for fixed-parameter tractability with respect to the corresponding parameter; we refer to Sect. 2 for the formal definitions.

Given an undirected graph G = (V, E) and a positive integer h, the Dominating Set problem asks whether there is a vertex subset \(V^{\prime}\subseteq V\) of size at most h such that for every \(v\in V\) it holds that \(v \in V^{\prime}\) or v is adjacent to a vertex in \(V^{\prime}. \)

For example, this is plausible for networks of teams (say in sports or work teams) where vertices are persons and there is an edge between two vertices if the intersection of their team membership durations is sufficiently large.

Given an undirected graph G = (V, E) and a positive integer h, the Vertex Cover problem asks whether there is a vertex subset \(V^{\prime}\subseteq V\) of size at most h such that each edge in E has at least one endpoint in \(V^{\prime}.\)

The dataset and a corresponding documentation are available online (http://dblp.uni-trier.de/xml/).

These three networks are available in the Pajek Dataset of Vladimir Batagelj and Andrej Mrvar (2006) (http://vlado.fmf.uni-lj.si/pub/networks/data/).

It is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernelization.

The cluster edge deletion number ξ is lower bounded by the cluster editing number \(\zeta, \) i.e., \(\xi \geq \zeta. \)

A bridge of a connected graph G is an edge whose deletion disconnects G.

Abrahamson KA, Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues. Ann Pure Appl Logic 73(3):235–276MathSciNetMATHCrossRef

Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theor Comput Sci 411(44–46):4017–4022MathSciNetMATHCrossRef

Agarwal N, Liu H, Tang L, Yu P (2011) Modeling blogger influence in a community. Soc Netw Anal Min (to appear)

Bazgan C, Chopin M, Fellows MR (2011) Parameterized complexity of the firefighter problem. In: Proceedings of 22nd ISAAC, LNCS, vol 7074. Springer, Berlin, pp 643–652

Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discrete Optim 8(1):87–96MathSciNetMATHCrossRef

Böcker S (2011) A golden ratio parameterized algorithm for cluster editing. In: Proceedings of 22nd IWOCA, LNCS, vol 7056. Springer, Berlin, pp 85–95

Böcker S, Damaschke P (2011) Even faster parameterized cluster deletion and cluster editing. Inf Process Lett 111(14):717–721MATHCrossRef

Bodlaender HL (2009) Kernelization: New upper and lower bound techniques. In: Proceedings of 4th IWPEC, LNCS, vol 5917. Springer, Berlin, pp 17–37

Bodlaender HL, Jansen BMP, Kratsch S (2011a) Preprocessing for treewidth: A combinatorial analysis through kernelization. In: Proceedings of 38th ICALP, LNCS, vol 6755. Springer, Berlin, pp 437–448

Bodlaender HL, Thomassé S, Yeo A (2011b) Kernel bounds for disjoint cycles and disjoint paths. Theor Comput Sci 412(35):4570–4578MATHCrossRef

Brandstädt A, Le VB, Spinrad JP (1999) Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications, vol 3. SIAM, Auckland

Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40–42):3736–3756MathSciNetMATHCrossRef

Chen N (2009) On the approximability of influence in social networks. SIAM J Discrete Math 23(3):1400–1415MathSciNetMATHCrossRef

Cygan M, Fomin F, Leeuwen EJV (2012) Parameterized complexity of firefighting revisited. In: Proceedings of 6th IPEC, LNCS, vol 7112. Springer, Berlin, pp 13–26

Davidson SB, Garcia-Molina H, Skeen D (1985) Consistency in partitioned networks. ACM Comput Surv 17(3):341–370CrossRef

De Nooy W, Mrvar A, Batagelj V (2011) Exploratory social network analysis with Pajek. No. 34 in structural analysis in the social sciences. Cambridge University Press, Cambridge

Dom M, Lokshtanov D, Saurabh S (2009) Incompressibility through colors and IDs. In: Proceedings of 36th ICALP, LNCS, vol 5555. Springer, Berlin, pp 378–389

Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of 7th ACM KDD. ACM Press, New York, pp 57–66

Downey R, Fellows M, McCartin C, Rosamond F (2008) Parameterized approximation of dominating set problems. Inf Process Lett 109(1):68–70MathSciNetCrossRef

Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin

Dreyer PA Jr, Roberts FS (2009) Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl Math 157:1615–1627MathSciNetMATHCrossRef

Easley D, Kleinberg J (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, Cambridge

Fellows M (2009) Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Proceedings of 20th IWOCA, LNCS, vol 5874. Springer, Berlin, pp 2–10

Fellows MR, Lokshtanov D, Misra N, Rosamond FA, Saurabh S (2008) Graph layout problems parameterized by vertex cover. In: Proceedings of 19th ISAAC, LNCS, vol 5369. Springer, Berlin, pp 294–305

Fiala J, Golovach PA, Kratochvíl J (2011) Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor Comput Sci 412(23):2513–2523MATHCrossRef

Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Berlin

Franks DW, Noble J, Kaufmann P, Stagl S (2008) Extremism propagation in social networks with hubs. Adapt Behav 16(4):264–274CrossRef

Garcia-Molina H, Barbará D (1985) How to assign votes in a distributed system. J ACM 32(4):841–860MATHCrossRef

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, Gordonsville

Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826MathSciNetMATHCrossRef

Guo J, Niedermeier R (2007) Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1):31–45CrossRef

Harant J, Pruchnewski A, Voigt M (1999) On dominating sets and independent sets of graphs. Comb Probab Comput 8(6):547–553MathSciNetMATHCrossRef

Jiang H, Zhang C, Zhu B (2010) Weak kernels. Tech. Rep. TR10-005, Department of Computer Science, Montana State University

Johnson DS (1984) The genealogy of theoretical computer science: a preliminary report. SIGACT News 16(2):36–49, reprinted in Bulletin of the EATCS, No. 25, pp 198–211, 1985

Jurvetson S (2000) What exactly is viral marketing? Red Herring 78:110–112

Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of 9th ACM KDD. ACM Press, New York, pp 137–146

Kutten S, Peleg D (1999) Fault-local distributed mending. J Algorithms 30(1):144–165MathSciNetMATHCrossRef

Leskovec J, Horvitz E (2008) Planetary-scale views on a large instant-messaging network. In: Proceedings of 17th WWW. ACM Press, New York, pp 915–924

Leskovec J, Adamic LA, Huberman BA (2007a) The dynamics of viral marketing. ACM Trans Web 1(1)

Leskovec J, McGlohon M, Faloutsos C, Glance NS, Hurst M (2007b) Patterns of cascading behavior in large blog graphs. In: Proceedings of 7th SDM. SIAM, Auckland, pp 551–556

MacGillivray G, Wang P (2003) On the firefighter problem. J Comb Math Comb Comput 47:83–96MathSciNetMATH

McConnell RM, Spinrad J (1994) Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Proceedings of 5th SODA. ACM/SIAM, New York, pp 536–545

Milgram S (1967) The small world problem. Psychol Today 1:61–67

Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256MathSciNetMATHCrossRef

Newman MEJ (2010) Networks: an introduction. Oxford University Press, Oxford

Newman MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68(3):036122CrossRef

Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, Oxford

Niedermeier R (2010) Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of 27th STACS, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, LIPIcs, vol 5, pp 17–32

Norlen K, Lucas G, Gebbie M, Chuang J (2002) Eva: extraction, visualization and analysis of the telecommunications and media ownership network. In: Proceedings of 14th ITS

Pelc A (1996) Efficient fault location with small risk. In: SIROCCO, Carleton Scientific, pp 292–300

Peleg D (2002) Local majorities, coalitions and monopolies in graphs: a review. Theor Comput Sci 282:231–257MathSciNetMATHCrossRef

Potterat JJ, Phillips-Plummer L, Muth SQ, Rothenberg RB, Woodhouse DE, Maldonado-Long TS, Zimmerman HP, Muth JB (2002) Risk network structure in the early epidemic phase of HIV transmission in Colorado Springs. Sex Transm Infect 78:159–163CrossRef

Raeder T, Chawla N (2011) Market basket analysis with networks. Soc Netw Anal Min 1:97–113CrossRef

Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of 8th ACM KDD. ACM Press, New York, pp 61–70

Shamir R, Sharan R, Tsur D (2004) Cluster graph modification problems. Discrete Appl Math 144(1–2):173–182MathSciNetMATHCrossRef

Tarjan RE (1974) A note on finding the bridges of a graph. Inf Process Lett 2(6):160–161MathSciNetMATHCrossRef

Uhlmann J, Weller M (2010) Two-layer planarization parameterized by feedback edge set. In: Proceedings of 7th TAMC, LNCS, vol 6108, Springer, Berlin, pp 431–442

Wang P, Moeller SA (2002) Fire control on graphs. J Comb Math Comb Comput 41:19–34MathSciNetMATH

Watts D, Peretti J, Frumin M (2007) Viral marketing for the real world. Harv Bus Rev 85(5):22–23

Zhang W, Wu W, Wang F, Xu K (2012) Positive influence dominating sets in power-law graphs. Soc Netw Anal Min 2(1):31–37MATHCrossRef

Titel: On tractable cases of Target Set Selection
verfasst von: André Nichterlein
Rolf Niedermeier
Johannes Uhlmann
Mathias Weller
Publikationsdatum: 01.06.2013
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 2/2013
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-012-0067-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2013

Complexity of social network anonymization

Improving network response times using social information

Altruism in social networks: good guys do finish first

A social network analysis and mining methodology for the monitoring of specific domains in the blogosphere

Web sessions clustering using hybrid sequence alignment measure (HSAM)

Application of data mining methods for link prediction in social networks

Premium Partner