Influence maximization on dynamic graphs - project 1

With the increasing popularity of social media and different emerging social networks, the impact of social influencers turns to more significant in people’s decision making process. In light of this opportunity, researchers have developed different methodologies to estimate influential spread of pe...

Full description

Saved in:
Bibliographic Details
Main Author: Cao, Gaoxu
Other Authors: Arijit Khan
Format: Final Year Project
Language:English
Published: 2017
Subjects:
Online Access:http://hdl.handle.net/10356/70505
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-70505
record_format dspace
spelling sg-ntu-dr.10356-705052023-03-03T20:59:32Z Influence maximization on dynamic graphs - project 1 Cao, Gaoxu Arijit Khan School of Computer Science and Engineering DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics With the increasing popularity of social media and different emerging social networks, the impact of social influencers turns to more significant in people’s decision making process. In light of this opportunity, researchers have developed different methodologies to estimate influential spread of people in social network, and to effectively identify the top-k influencers, who will maximize the influence among all social network users. However, in reality, the social networks have a highly dynamic nature and involve rapidly over time. The results based on one specific static graph will be outdated quickly. And The re-run of program on massive networks requires an expensive computational cost every time.In order to address this issue, researchers proposed new algorithms, such as DIM and OINT, which can effectively find the top-k influencers and estimate their influential spread in dynamic settings.In this project, a dataset of dynamic network graphs is firstly created from DBLP database. After that, some modifications and implementations are complemented on top of the paper authors’ code to ensure the both programs are able to run on the created dataset. Additionally, experimental evaluations using the created dynamic networks with millions of edges were done to demonstrate the efficiency, stability and accuracy of both DIM and OINT algorithms. The performance of two programs are compared with each other in detail as well. Based on the outcome of experiments, DIM algorithm provides a better performance in terms of the accuracy of influential spread estimation and required running time to identified the top-k influencers. It also provides a significant improvement over the static algorithms on time consumption for top-k influencers indemnification in dynamic settings and it does not cost much accuracy. Bachelor of Engineering (Computer Science) 2017-04-26T02:58:19Z 2017-04-26T02:58:19Z 2017 Final Year Project (FYP) http://hdl.handle.net/10356/70505 en Nanyang Technological University 54 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics
spellingShingle DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics
Cao, Gaoxu
Influence maximization on dynamic graphs - project 1
description With the increasing popularity of social media and different emerging social networks, the impact of social influencers turns to more significant in people’s decision making process. In light of this opportunity, researchers have developed different methodologies to estimate influential spread of people in social network, and to effectively identify the top-k influencers, who will maximize the influence among all social network users. However, in reality, the social networks have a highly dynamic nature and involve rapidly over time. The results based on one specific static graph will be outdated quickly. And The re-run of program on massive networks requires an expensive computational cost every time.In order to address this issue, researchers proposed new algorithms, such as DIM and OINT, which can effectively find the top-k influencers and estimate their influential spread in dynamic settings.In this project, a dataset of dynamic network graphs is firstly created from DBLP database. After that, some modifications and implementations are complemented on top of the paper authors’ code to ensure the both programs are able to run on the created dataset. Additionally, experimental evaluations using the created dynamic networks with millions of edges were done to demonstrate the efficiency, stability and accuracy of both DIM and OINT algorithms. The performance of two programs are compared with each other in detail as well. Based on the outcome of experiments, DIM algorithm provides a better performance in terms of the accuracy of influential spread estimation and required running time to identified the top-k influencers. It also provides a significant improvement over the static algorithms on time consumption for top-k influencers indemnification in dynamic settings and it does not cost much accuracy.
author2 Arijit Khan
author_facet Arijit Khan
Cao, Gaoxu
format Final Year Project
author Cao, Gaoxu
author_sort Cao, Gaoxu
title Influence maximization on dynamic graphs - project 1
title_short Influence maximization on dynamic graphs - project 1
title_full Influence maximization on dynamic graphs - project 1
title_fullStr Influence maximization on dynamic graphs - project 1
title_full_unstemmed Influence maximization on dynamic graphs - project 1
title_sort influence maximization on dynamic graphs - project 1
publishDate 2017
url http://hdl.handle.net/10356/70505
_version_ 1759857547727077376