Unit:
Κατεύθυνση Διαχείριση Δεδομένων, Πληροφορίας και ΓνώσηςΠληροφορική
Supervisors info:
Αλέξης Δελής, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Topic-Aware Influence Maximization Framework
Translated title:
Topic-Aware Influence Maximization Framework
Summary:
The focus of the thesis is given on the development of a novel framework to deal with the topic-aware influence maximization problem. The problem appears high computational complexity and belong in the area of social influence which involves both psychological and sociological aspects. In particular, the influence maximization problem aims to find a subset of nodes that maximize the expected spread of influence in a network.
Due to NP-hard computational complexity, the approximation algorithms are imperative to gain optimal or near-optimal solution with minor computational effort. In addition, real life networks should be used to provide valid results and significant information about how social influence is spread avoiding errors and problematic conclusions.
In the context of this thesis, the topic-aware influence maximization problem is studied and a novel framework based on the Hyperlink Induced Topic Search (HITS) algorithm is introduced. The proposed solution approach consists of two main components, i.e., the HITS algorithm and the Greedy or Cost Effective Lazy Forward (CELF) algorithms with modified Independent Cascade model in order to improve the results of the influence according to a topic. The HITS algorithm aims to analyze links and the Greedy and CELF algorithms to find the nodes that maximize the expected spread of influence in a network.
For the evaluation, the Neo4j graph database is used as a platform for the empirical experiments. Moreover, datasets of the Yelp social network alongside with generated graphs based on Barabási–Albert model provide the necessary data for testing. The computational results illustrate the pertinence of the developed algorithms and underline the role of the proposed framework’s components. Finally, it is worth to mention that the developed Greedy and CELF algorithms of this thesis have been contributed to the Neo4j open-source community.
Main subject category:
Technology - Computer science
Keywords:
Influence Maximization, Topic-Aware, Greedy, CELF, Independent Cascade model, HITS, Neo4j, Barabási–Albert model, Yelp dataset
