TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 01.02.2018

isti-logo

Page Content

to Navigation

Finding Critical Users for Social Network Engagement

Martin Reiche (TU Berlin)

 

Measuring engagement is an important step towards understanding the community of users in a social network. Assuming that social networks are only useful for the individual user if at least \(k\) of their contacts are part of the network, a straightforward measure of engagement, \(k\)-core, can be defined: \(k\)-core is the maximal induced subgraph in which every vertex has at least \(k\) neighbors. Based on \(k\)-core, this talk will introduce the Collapsed \(k\)-core problem which, given a limited budget \(b\), asks which \(b\) vertices in the graph have to be removed in order to get the smallest resulting \(k\)-core. The talk will show that Collapsed \(k\)-core is NP-hard but will introduce a greedy algorithm with \(O(bnm)\) running time which has been proven to provide good results on real social network datasets.

The talk is based on paper Finding Critical Users for Social Network Engagement: The Collapsed \(k\)-core Problem by Zhang et al. (AAAI '17)

 

Date
Speaker
Location
Language
01.02.2018
16:15
Martin Reiche
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe