A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering
Given a social network modelled by a graph, the goal of the influence maximization problem is to find <i>k</i> vertices that maximize the number of active vertices through a process of diffusion. For this diffusion, the linear threshold model is considered. A new algorithm, called Cluste...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/15/2/112 |
| _version_ | 1827343448550670336 |
|---|---|
| author | Agostinho Agra Jose Maria Samuco |
| author_facet | Agostinho Agra Jose Maria Samuco |
| author_sort | Agostinho Agra |
| collection | DOAJ |
| description | Given a social network modelled by a graph, the goal of the influence maximization problem is to find <i>k</i> vertices that maximize the number of active vertices through a process of diffusion. For this diffusion, the linear threshold model is considered. A new algorithm, called ClusterGreedy, is proposed to solve the influence maximization problem. The ClusterGreedy algorithm creates a partition of the original set of nodes into small subsets (the clusters), applies the SimpleGreedy algorithm to the subgraphs induced by each subset of nodes, and obtains the seed set from a combination of the seed set of each cluster by solving an integer linear program. This algorithm is further improved by exploring the submodularity property of the diffusion function. Experimental results show that the ClusterGreedy algorithm provides, on average, higher influence spread and lower running times than the SimpleGreedy algorithm on Watts–Strogatz random graphs. |
| first_indexed | 2024-03-07T22:27:25Z |
| format | Article |
| id | doaj.art-2d886709a6ed4f02b36b4240d1ddd378 |
| institution | Directory Open Access Journal |
| issn | 2078-2489 |
| language | English |
| last_indexed | 2024-03-07T22:27:25Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj.art-2d886709a6ed4f02b36b4240d1ddd3782024-02-23T15:21:09ZengMDPI AGInformation2078-24892024-02-0115211210.3390/info15020112A New Algorithm Framework for the Influence Maximization Problem Using Graph ClusteringAgostinho Agra0Jose Maria Samuco1Department of Mathematics, University of Aveiro, 3810-193 Aveiro, PortugalCenter for Research & Development in Mathematics and Applications, University of Aveiro, 3810-193 Aveiro, PortugalGiven a social network modelled by a graph, the goal of the influence maximization problem is to find <i>k</i> vertices that maximize the number of active vertices through a process of diffusion. For this diffusion, the linear threshold model is considered. A new algorithm, called ClusterGreedy, is proposed to solve the influence maximization problem. The ClusterGreedy algorithm creates a partition of the original set of nodes into small subsets (the clusters), applies the SimpleGreedy algorithm to the subgraphs induced by each subset of nodes, and obtains the seed set from a combination of the seed set of each cluster by solving an integer linear program. This algorithm is further improved by exploring the submodularity property of the diffusion function. Experimental results show that the ClusterGreedy algorithm provides, on average, higher influence spread and lower running times than the SimpleGreedy algorithm on Watts–Strogatz random graphs.https://www.mdpi.com/2078-2489/15/2/112clusterinfluence maximizationgreedy algorithmlinking setlinear threshold model |
| spellingShingle | Agostinho Agra Jose Maria Samuco A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering Information cluster influence maximization greedy algorithm linking set linear threshold model |
| title | A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering |
| title_full | A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering |
| title_fullStr | A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering |
| title_full_unstemmed | A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering |
| title_short | A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering |
| title_sort | new algorithm framework for the influence maximization problem using graph clustering |
| topic | cluster influence maximization greedy algorithm linking set linear threshold model |
| url | https://www.mdpi.com/2078-2489/15/2/112 |
| work_keys_str_mv | AT agostinhoagra anewalgorithmframeworkfortheinfluencemaximizationproblemusinggraphclustering AT josemariasamuco anewalgorithmframeworkfortheinfluencemaximizationproblemusinggraphclustering AT agostinhoagra newalgorithmframeworkfortheinfluencemaximizationproblemusinggraphclustering AT josemariasamuco newalgorithmframeworkfortheinfluencemaximizationproblemusinggraphclustering |