direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

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)


Martin Reiche
TEL 512

Back to the research colloquium site.

Nach oben

Zusatzinformationen / Extras