Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-Preventing Article Swipe
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2302.09620
In this paper, we propose a new influence spread model, namely, Complementary\&Competitive Independent Cascade (C$^2$IC) model. C$^2$IC model generalizes three well known influence model, i.e., influence boosting (IB) model, campaign oblivious (CO)IC model and the IC-N (IC model with negative opinions) model. This is the first model that considers both complementary and competitive influence spread comprehensively under multi-agent environment. Correspondingly, we propose the Complementary\&Competitive influence maximization (C$^2$IM) problem. Given an ally seed set and a rival seed set, the C$^2$IM problem aims to select a set of assistant nodes that can boost the ally spread and prevent the rival spread concurrently. We show the problem is NP-hard and can generalize the influence boosting problem and the influence blocking problem. With classifying the different cascade priorities into 4 cases by the monotonicity and submodularity (M\&S) holding conditions, we design 4 algorithms respectively, with theoretical approximation bounds provided. We conduct extensive experiments on real social networks and the experimental results demonstrate the effectiveness of the proposed algorithms. We hope this work can inspire abundant future exploration for constructing more generalized influence models that help streamline the works of this area.
Related Topics
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2302.09620
- https://arxiv.org/pdf/2302.09620
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4321473414
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4321473414Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2302.09620Digital Object Identifier
- Title
-
Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-PreventingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-02-19Full publication date if available
- Authors
-
Qihao Shi, Wenjie Tian, Wujian Yang, Mengqi Xue, Can Wang, Minghui WuList of authors in order
- Landing page
-
https://arxiv.org/abs/2302.09620Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2302.09620Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2302.09620Direct OA link when available
- Concepts
-
Boosting (machine learning), Maximization, Computer science, Cascade, Mathematical optimization, Monotonic function, Set (abstract data type), Artificial intelligence, Mathematics, Engineering, Mathematical analysis, Chemical engineering, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4321473414 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2302.09620 |
| ids.doi | https://doi.org/10.48550/arxiv.2302.09620 |
| ids.openalex | https://openalex.org/W4321473414 |
| fwci | |
| type | preprint |
| title | Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-Preventing |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12592 |
| topics[0].field.id | https://openalex.org/fields/31 |
| topics[0].field.display_name | Physics and Astronomy |
| topics[0].score | 0.9991000294685364 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/3109 |
| topics[0].subfield.display_name | Statistical and Nonlinear Physics |
| topics[0].display_name | Opinion Dynamics and Social Influence |
| topics[1].id | https://openalex.org/T10064 |
| topics[1].field.id | https://openalex.org/fields/31 |
| topics[1].field.display_name | Physics and Astronomy |
| topics[1].score | 0.9986000061035156 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/3109 |
| topics[1].subfield.display_name | Statistical and Nonlinear Physics |
| topics[1].display_name | Complex Network Analysis Techniques |
| topics[2].id | https://openalex.org/T10557 |
| topics[2].field.id | https://openalex.org/fields/33 |
| topics[2].field.display_name | Social Sciences |
| topics[2].score | 0.9879000186920166 |
| topics[2].domain.id | https://openalex.org/domains/2 |
| topics[2].domain.display_name | Social Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/3315 |
| topics[2].subfield.display_name | Communication |
| topics[2].display_name | Social Media and Politics |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C46686674 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9070924520492554 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q466303 |
| concepts[0].display_name | Boosting (machine learning) |
| concepts[1].id | https://openalex.org/C2776330181 |
| concepts[1].level | 2 |
| concepts[1].score | 0.738974928855896 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q18358244 |
| concepts[1].display_name | Maximization |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.6273627877235413 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C34146451 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6165516972541809 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q5048094 |
| concepts[3].display_name | Cascade |
| concepts[4].id | https://openalex.org/C126255220 |
| concepts[4].level | 1 |
| concepts[4].score | 0.5129380226135254 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[4].display_name | Mathematical optimization |
| concepts[5].id | https://openalex.org/C72169020 |
| concepts[5].level | 2 |
| concepts[5].score | 0.49325793981552124 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q194404 |
| concepts[5].display_name | Monotonic function |
| concepts[6].id | https://openalex.org/C177264268 |
| concepts[6].level | 2 |
| concepts[6].score | 0.46822378039360046 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[6].display_name | Set (abstract data type) |
| concepts[7].id | https://openalex.org/C154945302 |
| concepts[7].level | 1 |
| concepts[7].score | 0.2947842478752136 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[7].display_name | Artificial intelligence |
| concepts[8].id | https://openalex.org/C33923547 |
| concepts[8].level | 0 |
| concepts[8].score | 0.24008315801620483 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[8].display_name | Mathematics |
| concepts[9].id | https://openalex.org/C127413603 |
| concepts[9].level | 0 |
| concepts[9].score | 0.08630228042602539 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[9].display_name | Engineering |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| concepts[11].id | https://openalex.org/C42360764 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q83588 |
| concepts[11].display_name | Chemical engineering |
| concepts[12].id | https://openalex.org/C199360897 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[12].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/boosting |
| keywords[0].score | 0.9070924520492554 |
| keywords[0].display_name | Boosting (machine learning) |
| keywords[1].id | https://openalex.org/keywords/maximization |
| keywords[1].score | 0.738974928855896 |
| keywords[1].display_name | Maximization |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.6273627877235413 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/cascade |
| keywords[3].score | 0.6165516972541809 |
| keywords[3].display_name | Cascade |
| keywords[4].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[4].score | 0.5129380226135254 |
| keywords[4].display_name | Mathematical optimization |
| keywords[5].id | https://openalex.org/keywords/monotonic-function |
| keywords[5].score | 0.49325793981552124 |
| keywords[5].display_name | Monotonic function |
| keywords[6].id | https://openalex.org/keywords/set |
| keywords[6].score | 0.46822378039360046 |
| keywords[6].display_name | Set (abstract data type) |
| keywords[7].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[7].score | 0.2947842478752136 |
| keywords[7].display_name | Artificial intelligence |
| keywords[8].id | https://openalex.org/keywords/mathematics |
| keywords[8].score | 0.24008315801620483 |
| keywords[8].display_name | Mathematics |
| keywords[9].id | https://openalex.org/keywords/engineering |
| keywords[9].score | 0.08630228042602539 |
| keywords[9].display_name | Engineering |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2302.09620 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2302.09620 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2302.09620 |
| locations[1].id | doi:10.48550/arxiv.2302.09620 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2302.09620 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5065451770 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-7883-9848 |
| authorships[0].author.display_name | Qihao Shi |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Shi, Qihao |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100556321 |
| authorships[1].author.orcid | https://orcid.org/0009-0009-0174-7310 |
| authorships[1].author.display_name | Wenjie Tian |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Tian, Wenjie |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5065976782 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-9107-6849 |
| authorships[2].author.display_name | Wujian Yang |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Yang, Wujian |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5040860593 |
| authorships[3].author.orcid | https://orcid.org/0000-0003-4936-4887 |
| authorships[3].author.display_name | Mengqi Xue |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Xue, Mengqi |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5100428572 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-2890-0057 |
| authorships[4].author.display_name | Can Wang |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Wang, Can |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5101925641 |
| authorships[5].author.orcid | https://orcid.org/0000-0001-8179-7119 |
| authorships[5].author.display_name | Minghui Wu |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Wu, Minghui |
| authorships[5].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2302.09620 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2023-02-23T00:00:00 |
| display_name | Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-Preventing |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12592 |
| primary_topic.field.id | https://openalex.org/fields/31 |
| primary_topic.field.display_name | Physics and Astronomy |
| primary_topic.score | 0.9991000294685364 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/3109 |
| primary_topic.subfield.display_name | Statistical and Nonlinear Physics |
| primary_topic.display_name | Opinion Dynamics and Social Influence |
| related_works | https://openalex.org/W2153719181, https://openalex.org/W1971748923, https://openalex.org/W1566155057, https://openalex.org/W2060986072, https://openalex.org/W2125652721, https://openalex.org/W2052574922, https://openalex.org/W1540371141, https://openalex.org/W64588465, https://openalex.org/W4231274751, https://openalex.org/W3120641340 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2302.09620 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2302.09620 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2302.09620 |
| primary_location.id | pmh:oai:arXiv.org:2302.09620 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2302.09620 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2302.09620 |
| publication_date | 2023-02-19 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.4 | 126, 138 |
| abstract_inverted_index.a | 5, 74, 84 |
| abstract_inverted_index.In | 0 |
| abstract_inverted_index.We | 101, 146, 165 |
| abstract_inverted_index.an | 69 |
| abstract_inverted_index.by | 128 |
| abstract_inverted_index.is | 43, 105 |
| abstract_inverted_index.of | 86, 161, 185 |
| abstract_inverted_index.on | 150 |
| abstract_inverted_index.to | 82 |
| abstract_inverted_index.we | 3, 60, 136 |
| abstract_inverted_index.(IC | 36 |
| abstract_inverted_index.and | 33, 51, 73, 95, 107, 114, 131, 154 |
| abstract_inverted_index.can | 90, 108, 169 |
| abstract_inverted_index.for | 174 |
| abstract_inverted_index.new | 6 |
| abstract_inverted_index.set | 72, 85 |
| abstract_inverted_index.the | 34, 44, 62, 78, 92, 97, 103, 110, 115, 121, 129, 155, 159, 162, 183 |
| abstract_inverted_index.(IB) | 27 |
| abstract_inverted_index.IC-N | 35 |
| abstract_inverted_index.This | 42 |
| abstract_inverted_index.With | 119 |
| abstract_inverted_index.aims | 81 |
| abstract_inverted_index.ally | 70, 93 |
| abstract_inverted_index.both | 49 |
| abstract_inverted_index.help | 181 |
| abstract_inverted_index.hope | 166 |
| abstract_inverted_index.into | 125 |
| abstract_inverted_index.more | 176 |
| abstract_inverted_index.real | 151 |
| abstract_inverted_index.seed | 71, 76 |
| abstract_inverted_index.set, | 77 |
| abstract_inverted_index.show | 102 |
| abstract_inverted_index.that | 47, 89, 180 |
| abstract_inverted_index.this | 1, 167, 186 |
| abstract_inverted_index.well | 20 |
| abstract_inverted_index.with | 38, 141 |
| abstract_inverted_index.work | 168 |
| abstract_inverted_index.Given | 68 |
| abstract_inverted_index.area. | 187 |
| abstract_inverted_index.boost | 91 |
| abstract_inverted_index.cases | 127 |
| abstract_inverted_index.first | 45 |
| abstract_inverted_index.i.e., | 24 |
| abstract_inverted_index.known | 21 |
| abstract_inverted_index.model | 17, 32, 37, 46 |
| abstract_inverted_index.nodes | 88 |
| abstract_inverted_index.rival | 75, 98 |
| abstract_inverted_index.three | 19 |
| abstract_inverted_index.under | 56 |
| abstract_inverted_index.works | 184 |
| abstract_inverted_index.(CO)IC | 31 |
| abstract_inverted_index.bounds | 144 |
| abstract_inverted_index.design | 137 |
| abstract_inverted_index.future | 172 |
| abstract_inverted_index.model, | 9, 23, 28 |
| abstract_inverted_index.model. | 15, 41 |
| abstract_inverted_index.models | 179 |
| abstract_inverted_index.paper, | 2 |
| abstract_inverted_index.select | 83 |
| abstract_inverted_index.social | 152 |
| abstract_inverted_index.spread | 8, 54, 94, 99 |
| abstract_inverted_index.C$^2$IC | 16 |
| abstract_inverted_index.C$^2$IM | 79 |
| abstract_inverted_index.Cascade | 13 |
| abstract_inverted_index.NP-hard | 106 |
| abstract_inverted_index.cascade | 123 |
| abstract_inverted_index.conduct | 147 |
| abstract_inverted_index.holding | 134 |
| abstract_inverted_index.inspire | 170 |
| abstract_inverted_index.namely, | 10 |
| abstract_inverted_index.prevent | 96 |
| abstract_inverted_index.problem | 80, 104, 113 |
| abstract_inverted_index.propose | 4, 61 |
| abstract_inverted_index.results | 157 |
| abstract_inverted_index.abundant | 171 |
| abstract_inverted_index.blocking | 117 |
| abstract_inverted_index.boosting | 26, 112 |
| abstract_inverted_index.campaign | 29 |
| abstract_inverted_index.negative | 39 |
| abstract_inverted_index.networks | 153 |
| abstract_inverted_index.problem. | 67, 118 |
| abstract_inverted_index.proposed | 163 |
| abstract_inverted_index.(C$^2$IC) | 14 |
| abstract_inverted_index.(C$^2$IM) | 66 |
| abstract_inverted_index.assistant | 87 |
| abstract_inverted_index.considers | 48 |
| abstract_inverted_index.different | 122 |
| abstract_inverted_index.extensive | 148 |
| abstract_inverted_index.influence | 7, 22, 25, 53, 64, 111, 116, 178 |
| abstract_inverted_index.oblivious | 30 |
| abstract_inverted_index.opinions) | 40 |
| abstract_inverted_index.provided. | 145 |
| abstract_inverted_index.(M\&S) | 133 |
| abstract_inverted_index.algorithms | 139 |
| abstract_inverted_index.generalize | 109 |
| abstract_inverted_index.priorities | 124 |
| abstract_inverted_index.streamline | 182 |
| abstract_inverted_index.Independent | 12 |
| abstract_inverted_index.algorithms. | 164 |
| abstract_inverted_index.classifying | 120 |
| abstract_inverted_index.competitive | 52 |
| abstract_inverted_index.conditions, | 135 |
| abstract_inverted_index.demonstrate | 158 |
| abstract_inverted_index.experiments | 149 |
| abstract_inverted_index.exploration | 173 |
| abstract_inverted_index.generalized | 177 |
| abstract_inverted_index.generalizes | 18 |
| abstract_inverted_index.multi-agent | 57 |
| abstract_inverted_index.theoretical | 142 |
| abstract_inverted_index.constructing | 175 |
| abstract_inverted_index.environment. | 58 |
| abstract_inverted_index.experimental | 156 |
| abstract_inverted_index.maximization | 65 |
| abstract_inverted_index.monotonicity | 130 |
| abstract_inverted_index.approximation | 143 |
| abstract_inverted_index.complementary | 50 |
| abstract_inverted_index.concurrently. | 100 |
| abstract_inverted_index.effectiveness | 160 |
| abstract_inverted_index.respectively, | 140 |
| abstract_inverted_index.submodularity | 132 |
| abstract_inverted_index.comprehensively | 55 |
| abstract_inverted_index.Correspondingly, | 59 |
| abstract_inverted_index.Complementary\&Competitive | 11, 63 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 6 |
| citation_normalized_percentile |