Sie sind hier

# 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