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)
Back to the research colloquium site.