Unifying information propagation models on networks and influence maximisation
Information propagation on networks is a central theme in social, behavioural, and economic sciences, with important theoretical and practical implications, such as the influence maximisation problem for viral marketing. Here, we consider a model that unifies the classical independent cascade models...
| Main Authors: | , |
|---|---|
| Format: | Internet publication |
| Language: | English |
| Published: |
2021
|
| _version_ | 1797107187106971648 |
|---|---|
| author | Tian, Y Lambiotte, R |
| author_facet | Tian, Y Lambiotte, R |
| author_sort | Tian, Y |
| collection | OXFORD |
| description | Information propagation on networks is a central theme in social, behavioural, and economic sciences, with important theoretical and practical implications, such as the influence maximisation problem for viral marketing. Here, we consider a model that unifies the classical independent cascade models and the linear threshold models, and generalise them by considering continuous variables and allowing feedback in the dynamics. We then formulate its influence maximisation as a mixed integer nonlinear programming problem and adopt derivative-free methods. Furthermore, we show that the problem can be exactly solved in the special case of linear dynamics, where the selection criteria is closely related to the Katz centrality, and propose a customised direct search method with local convergence. We then demonstrate the close-to-optimal performance of the customised direct search numerically on both synthetic and real networks. |
| first_indexed | 2024-03-07T07:12:24Z |
| format | Internet publication |
| id | oxford-uuid:82922f55-68ae-44cb-8514-d5acfbc26a87 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:12:24Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | oxford-uuid:82922f55-68ae-44cb-8514-d5acfbc26a872022-07-01T11:09:02ZUnifying information propagation models on networks and influence maximisationInternet publicationhttp://purl.org/coar/resource_type/c_7ad9uuid:82922f55-68ae-44cb-8514-d5acfbc26a87EnglishSymplectic Elements2021Tian, YLambiotte, RInformation propagation on networks is a central theme in social, behavioural, and economic sciences, with important theoretical and practical implications, such as the influence maximisation problem for viral marketing. Here, we consider a model that unifies the classical independent cascade models and the linear threshold models, and generalise them by considering continuous variables and allowing feedback in the dynamics. We then formulate its influence maximisation as a mixed integer nonlinear programming problem and adopt derivative-free methods. Furthermore, we show that the problem can be exactly solved in the special case of linear dynamics, where the selection criteria is closely related to the Katz centrality, and propose a customised direct search method with local convergence. We then demonstrate the close-to-optimal performance of the customised direct search numerically on both synthetic and real networks. |
| spellingShingle | Tian, Y Lambiotte, R Unifying information propagation models on networks and influence maximisation |
| title | Unifying information propagation models on networks and influence
maximisation |
| title_full | Unifying information propagation models on networks and influence
maximisation |
| title_fullStr | Unifying information propagation models on networks and influence
maximisation |
| title_full_unstemmed | Unifying information propagation models on networks and influence
maximisation |
| title_short | Unifying information propagation models on networks and influence
maximisation |
| title_sort | unifying information propagation models on networks and influence maximisation |
| work_keys_str_mv | AT tiany unifyinginformationpropagationmodelsonnetworksandinfluencemaximisation AT lambiotter unifyinginformationpropagationmodelsonnetworksandinfluencemaximisation |