Athens University Economics and Business (AUEB)
Graph mining In complex networks and prediction in the web graph
Abstract
dc:descriptionThe study of real world networks has attracted considerable attention over the last decades from many disciplines including biology, computer science, economics, engineering, mathematics, physics, sociology and statistics. The need for their investigation gave prominence to the Graph Mining field which constitutes a very powerful tool of data representation (as graphs). Graphs have become very important in modeling complicated structures and analyzing the topological characteristics of large and complex networks and especially in recent years, with the vast growth of the World Wide Web and the popularity of social networks. In the latter type of networks, large amounts of information and data are shared and transferred among millions or even billions of users. The simplest way to analyze them is through their conversion to graphs, where the nodes represent the users and the edges between pairs of nodes describe the relations (friendships).In the first part of this thesis, we focus on the investigation of homophily in a subgraph of Facebook collected via the Breadth First Search. By applying a community detection algorithm and based just on the graph structure, we intend to examine the correlation between the social network communities and the users’ characteristics represented by Likes. More specifically, we take into account the users’ top preferences (Likes) in each community and the categories corresponding to the Likes. Next, we assign a score on the distinct Likes and categories, based on their popularity within the community. The experimental results show that in the case of users’ Likes, the correlation ranges from small to medium between communities and the whole population (Facebook crawled subgraph), while it is even smaller between communities. However, there is a high correlation in terms of Like categoriesbetween the different communities and between communities and the overall population. This fact proves that Likes constitute a criterion of distinction among the communities and verify the intuition that led us towards this research.In the second part, we crawled a large dataset from the Facebook graph consisting of 10 million users and 80 million users’ relations. In order to discover important topological properties of this huge graph and other large real networks, we were directed towards the study of graph sampling methods. The initial attempt resulted in the development of Rank Degree, a new graph exploration sampling algorithm which is based on edge selection. The experimental evaluation on several real datasets and the comparison with five efficient graph sampling techniques proves that our approach maintains several properties of the initial graph, leading to representative samples and outperforms among the five approaches. Extending this study, we performed a deeper search into all the advantages of Rank Degree. Specifically, we present the results of exhaustive experiments and compare the Rank Degree with more complex and efficient methods in the graph sampling scientific area, such as theMetropolis-Hastings algorithm, in many real-world datasets of different type and size and using a variety of measures.Furthermore, we deal with the problem of identifying the influential spreaders of a complex network under a different scope as it is used in previous works. Our approach is based on graph sampling and specifically, on the superior properties of Rank Degree. Initially, we conduct extensive experiments on five real-world networks and we use four centrality metrics for the influences of nodes. We provide strong evidence that our method is highly effective. The continuity of this study spreads to epidemic models such as SIR and SIS, which possess the significant property of exploring all the nodes of a graph and discover the most important ones. Using them as ground truth identifiers, we compare the resulted important nodes with those produced by the samples of Rank Degree and other intricate and efficient methods. The results prove that our algorithm is superior towards other methods and is even able to be compared with such crucial models, discriminating the influential spreaders of large network graphs.In the last part, the problem of important node discovery is transferred to the Web graph and is examined under a different scope. Applying crawling, we gather the results (webpages) coming out of various queries on popular search engines (Google, Yahoo) and specifically, the top webpages and their ranking in successive timestamps. Obviously, the webpages (nodes) considered to be the most important in the Web graph appear in the first positions of the proposed links for the given queries. Exploiting this local information, we propose different machine learning methodologies in order to predict whether the nodes of a non-static graph, as the Web is, will remain in the top positions in the near future. The prediction quality is quantified as the similarity between the predicted and the actual rankings. We carry out extensive experiments on real-world large scale datasets. In addition, we use a variety of existing similarity measures for comparing the top-k nodes, while we introduce a new one which is stricter. The predictions are encouraging in all experimental setups and similaritymeasures. Moreover, the results offer many interesting tasks for future investigation in graphs which are not static, but evolve through time.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Voudigari, Elli
- Βουδιγάρη, Έλλη
Subjects
dc:subject × 7Rights
dc:rights- Statement dc:rights
-
- BY_NC_ND
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/44611