Title page for etd-0115116-163418


[Back to Results | New Search]

URN etd-0115116-163418
Author You-Chuan Yang
Author's Email Address No Public.
Statistics This thesis had been viewed 5537 times. Download 0 times.
Department Computer Science and Engineering
Year 2015
Semester 1
Degree Master
Type of Document
Language zh-TW.Big5 Chinese
Title A NewGreedy Genetic Algorithm for Influence Maximization in Social Network
Date of Defense 2016-01-15
Page Count 53
Keyword
  • influence maximization problem
  • social network
  • meta-heuristic algorithm
  • genetic algorithm
  • NewGreedy algorithm
  • propagation model
  • Abstract With the advance of computer and internet technologies, social networks have become an integral part of most people‚Äôs life. People can now use social networks to send out messages. They can also share pictures or articles with their friends. For this reason, many businessmen advertise their products by the social networks. As such, one of the critical research topics that come up is how to find people that have the largest influence; i.e., the so-called influence maximization problem. The goal of this problem is to find a k-size seed set which has a maxi-
    mum influence with respect to a particular propagation model. For the influence maximization problem is NP-hard, it is obvious that an exhausted search algorithm is not able to fine the solution in a reasonable time. In order to solve this problem, some researchers rely on greedy algorithms to find a approximate solution for this problem, but the quality of the solution is simply not good enough. Hence, a high-performance algorithm for solving the influence maximization problem, which leverages the strength of the new greedy algorithm and the genetic algorithm (GA), is presented in this thesis. Experimental results show that the proposed algorithm outperforms simple GA by about 10% in terms of the quality, with the speed that is faster than many meta-heuristic algorithms.
    Advisory Committee
  • Chu-Sing Yang - chair
  • Chun-Wei Tsai - co-chair
  • Ming-Chao Chiang - advisor
  • Files
  • etd-0115116-163418.pdf
  • Indicate in-campus at 99 year and off-campus access at 99 year.
    Date of Submission 2016-02-15

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys