Influence maximization on dynamic graphs
In the real world, there are many applications of the stream such as social networks and telecommunication networks. Due to the great potential in targeted recommendations and viral marketing, there is a tremendous incentive to find the top k influencers. However, due to the nature of the dynamic gr...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/70093 |
| _version_ | 1811697785968263168 |
|---|---|
| author | Lim, Zi Xiang |
| author2 | Arijit Khan |
| author_facet | Arijit Khan Lim, Zi Xiang |
| author_sort | Lim, Zi Xiang |
| collection | NTU |
| description | In the real world, there are many applications of the stream such as social networks and telecommunication networks. Due to the great potential in targeted recommendations and viral marketing, there is a tremendous incentive to find the top k influencers. However, due to the nature of the dynamic graph, we will tackle the inherent problem of finding the top k influencers as the dynamic graph is constantly changing. We model the stream as slip shots of the static graph that changes over the time. From there, we take note of the incoming changes to the edges and attempt in handling those mutually exclusive cases. Under the popular use of the independent cascade model, we develop an algorithm that performs an update to the top k nodes based on the mutually exclusive cases of edge addition, edge deletion and edge modification. Using up to date research by other paper and the DBLP collaboration network dataset, we validate the use of our method on the network and present a timeline of the most influential authors in the network. |
| first_indexed | 2024-10-01T08:00:47Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/70093 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T08:00:47Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | ntu-10356/700932023-03-03T20:54:34Z Influence maximization on dynamic graphs Lim, Zi Xiang Arijit Khan School of Computer Science and Engineering DRNTU::Engineering::Computer science and engineering In the real world, there are many applications of the stream such as social networks and telecommunication networks. Due to the great potential in targeted recommendations and viral marketing, there is a tremendous incentive to find the top k influencers. However, due to the nature of the dynamic graph, we will tackle the inherent problem of finding the top k influencers as the dynamic graph is constantly changing. We model the stream as slip shots of the static graph that changes over the time. From there, we take note of the incoming changes to the edges and attempt in handling those mutually exclusive cases. Under the popular use of the independent cascade model, we develop an algorithm that performs an update to the top k nodes based on the mutually exclusive cases of edge addition, edge deletion and edge modification. Using up to date research by other paper and the DBLP collaboration network dataset, we validate the use of our method on the network and present a timeline of the most influential authors in the network. Bachelor of Engineering (Computer Science) 2017-04-11T05:17:28Z 2017-04-11T05:17:28Z 2017 Final Year Project (FYP) http://hdl.handle.net/10356/70093 en Nanyang Technological University 46 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Lim, Zi Xiang Influence maximization on dynamic graphs |
| title | Influence maximization on dynamic graphs |
| title_full | Influence maximization on dynamic graphs |
| title_fullStr | Influence maximization on dynamic graphs |
| title_full_unstemmed | Influence maximization on dynamic graphs |
| title_short | Influence maximization on dynamic graphs |
| title_sort | influence maximization on dynamic graphs |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | http://hdl.handle.net/10356/70093 |
| work_keys_str_mv | AT limzixiang influencemaximizationondynamicgraphs |