A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the topic is likely to occur. In this paper, we consider the task of selecting initial seed users of a topic with minimum size so that with a guaranteed probability the number of users discussing the topic would reach a given threshold. We formulate the task as an optimization problem called seed minimization with probabilistic coverage guarantee (SM-PCG). This problem departs from the previous studies on social in\ufb02uence maximization or seed minimization because it considers in\ufb02uence coverage with probabilistic guarantees instead of guarantees on expected in\ufb02uence coverage. We show that the problem is not submodular, and thus is harder than previously studied problems based on submodular function optimization. We provide an approximation algorithm and show that it approximates the optimal solution with both a multiplicative ratio and an additive error. The multiplicative ratio is tight while the additive error would be small if in\ufb02uence coverage distributions of certain seed sets are well concentrated. For one-way bipartite graphs we analytically prove the concentration condition and obtain an approximation algorithm with an O(log n) multiplicative ratio and an O(\u221an) additive error, where n is the total number of nodes in the social graph. Moreover, we empirically verify the concentration condition in real-world networks and experimentally demonstrate the e\ufb00ectiveness of our proposed algorithm comparing to commonly adopted benchmark algorithms.<\/p>\n","protected":false},"excerpt":{"rendered":"
A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the topic is likely to occur. In this paper, we consider the task of selecting initial seed users of a topic with minimum size […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"KDD\u201914, August 24\u201327, 2014, New York, NY, USA.","msr_publisher_other":"","msr_booktitle":"Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2014)","msr_chapter":"","msr_edition":"In Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2014), New York City, New York, U.S.A., August, 2014.","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"Copyright 2014 ACM","msr_conference_name":"Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2014)","msr_doi":"10.1145\/2623330.2623684","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2014-08-24","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"http:\/\/arxiv.org\/abs\/1402.5516","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561,13559],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-246398","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-social-sciences","msr-locale-en_us"],"msr_publishername":"KDD\u201914, August 24\u201327, 2014, New York, NY, USA.","msr_edition":"In Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2014), New York City, New York, U.S.A., August, 2014.","msr_affiliation":"","msr_published_date":"2014-08-24","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'2014)","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"457458","msr_publicationurl":"http:\/\/arxiv.org\/abs\/1402.5516","msr_doi":"10.1145\/2623330.2623684","msr_publication_uploader":[{"type":"file","title":"Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/06\/kdd14_probcoverage.pdf","id":457458,"label_id":0},{"type":"url","title":"http:\/\/arxiv.org\/abs\/1402.5516","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1145\/2623330.2623684","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"http:\/\/arxiv.org\/abs\/1402.5516"}],"msr-author-ordering":[{"type":"text","value":"Peng Zhang","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Wei Chen","user_id":34795,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Wei Chen"},{"type":"text","value":"Xiaoming Sun","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Yajun Wang","user_id":34953,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Yajun Wang"},{"type":"text","value":"Jialin Zhang","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[802999],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/246398","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/246398\/revisions"}],"predecessor-version":[{"id":479784,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/246398\/revisions\/479784"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=246398"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=246398"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=246398"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=246398"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=246398"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=246398"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=246398"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=246398"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=246398"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=246398"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=246398"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=246398"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=246398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}