Project topics and materials
Get Complete Project Material File(s) Now! »
basic concepts in graph theory
A network is usually represented by a graph (throughout the dissertation we use the terms network and graph interchangeably). A graph G = (V, E) consists of a set of nodes V and a set of edges E V V which connect pairs of nodes (in some cases, the nodes and edges of a graph are also called vertices and links respectively). The number of nodes in the graph is equal to n = jVj and the number of edges m = jEj. A graph may be directed or undirected, unipartite or bipartite and the edges may contain weights or not. Figure 2.1 depicts some examples of different types of graphs.
related work
In this section we review the related work, regarding the engagement dynamics in social graphs, as well as other applications of the k-core decomposition. In the very recent literature, there has been presented some game-theoretic models for the problem of product adoption in networked environments [MJ09; Har13; Bha+11]. These models form the basis of our approach and are described in detail in Section 3.4. To the best of our knowledge, the only related work that provides experimental study for the problem of node departures in social networks, is the work presented in [Wu+13]. There, the authors study two real social networks and examine whether the departure dynamics show similar behavior with the arrival dynamics. In the case of node departures, the authors of [Wu+13] observed that the active users typically belong to a dense core of the graph, while inactive users are placed on the sparsely connected periphery of the graph. As we will present later, the property of node engagement can be considered complementary to the one of node departure, and our approach provides a more refined modeling of the observations made in [Wu+13]. Moreover, related to our work can be considered recent studies about the formation dynamics of communities [Bac+06; LS09], as well as studies about diffusion and contagion in social graphs [Uga+12; AKM08; RMK11; EK10]. As we will present in Section 3.4, our method builds upon the properties of the k-core decomposition in a graph (see Section 3.3 for more details). Broadly speaking, the k-core decomposition has been applied in the past for extracting the most coherent subgraphs [Sei83], graph visualization [ZP12], identification of influential spreaders [Kit+10], and for studying [AH+08] and modeling [Car+07] the Internet topology. In this work, we examine one more application domain of the k-core decomposition in the problem of node engagement in social graphs; in contrast to the previous studies that mostly focus on the nodes of the best k-core subgraph, in this work we are interested in the hierarchy produced by the decomposition, since it can provide meaningful insights about the engagement dynamics of the graph.
preliminaries and background
In this section we briefly discuss the properties of the k-core decomposition [Sei83], which is utilized by our method. For completeness in the presentation, next we repeat the definitions regarding the main concepts of the k-core decomposition used in this Chapter (see also Chapter 2, Section 2.3 for a detailed description). Let G = (V, E) be an undirected graph, where jVj = n, jEj = m and let graph H be a subgraph of G. A subgraph H is defined to be a k-core of G if it is a maximal connected subgraph of G, in which all nodes have degree at least k. The degeneracy d(G) of a graph G is defined as the maximum k for which graph G contains a non-empty k-core subgraph. A node i has core number ci = k, if it belongs to a k-core but not to any (k + 1)-core.
As we have already described, the k-core of a graph G can be obtained by repeatedly deleting all nodes with degree less than k. Furthermore, the k-core decomposition – which assigns a core number ci to each node i 2 V – can be computed efficiently, with complexity O(m) proportional to the size of the graph [BZ03]. The most important point is that the k-core decomposition creates an hierarchy of the graph, where “better” k-core subgraphs (i.e., higher values of k) correspond to more cohesive parts of the graph.
Table of contents :
1 introduction
1.1 Thesis Statement and Overview of Contributions
1.1.1 Dynamics of Real Networks
1.1.2 Graph-Based Algorithmic Tools for Data Analytics
1.2 Outline of the Thesis
2 basic concepts and preliminaries
2.1 Basic Concepts in Graph Theory
2.2 Linear Algebra: Eigenvalues and Singular Values
2.3 Core Decomposition in Networks
2.3.1 Fundamental Concepts and Algorithms
2.3.2 Applications
2.4 Description of Graph Datasets
3 modeling engagement dynamics in social graphs
3.1 Introduction
3.2 Related Work
3.3 Preliminaries and Background
3.4 Problem Formulation and Proposed Method
3.4.1 Problem Statement and Model Description
3.4.2 Engagement Measures
3.4.3 Discussion
3.5 Engagement of Real Graphs
3.5.1 High Level Properties of k-Engagement Subgraphs
3.5.2 Graph’s Engagement Properties
3.5.3 Near Self Similar k-Engagement Subgraphs
3.5.4 Engagement and Clustering Structures
3.6 Disengagement Social Contagion
3.7 Conclusions and Future Work
4 vulnerability assessment in social networks under cascade- based node departures
4.1 Introduction
4.2 Related Work
4.3 Disengagement Epidemic Model
4.4 Vulnerability Assessment under Node Departures
4.4.1 Observations on Real Graphs
4.4.2 Social Vulnerability Assessment
4.4.3 Experimental Results
4.5 Conclusions and Discussion
5 locating influential spreaders in social networks
5.1 Introduction
5.2 Preliminaries and Background
5.2.1 K-truss Decomposition
5.2.2 Epidemic Models
5.3 Related Work
5.3.1 Identifying Individual Spreaders in Networks
5.3.2 Influence Propagation Models and Influence Maximization in Networks
5.4 K-truss Decomposition for Identifying Influential Nodes
5.5 Experimental Evaluation
5.5.1 Datasets and Baseline Methods
5.5.2 Characteristics of K-truss Subgraphs
5.5.3 Evaluating the Spreading Performance
5.5.4 Comparison to the Optimal Spreading
5.5.5 Impact of Infection and Recovery Rate on the Spreading Process
5.6 Conclusions and Future Work
6 a graph-based framework for text categorization
6.1 Introduction
6.2 Related Work
6.3 Preliminaries and Background
6.3.1 Text Categorization Pipeline and Term Weighting in the Bag-of-Words Model
6.3.2 Graph-Theoretic Concepts
6.4 Proposed Framework for Text Categorization
6.4.1 Graph Construction
6.4.2 Term Weighting
6.4.3 Inverse Collection Weight (ICW)
6.4.4 Unsupervised Feature Selection
6.4.5 Computational Complexity
6.4.6 Classification Algorithms
6.5 Experimental Evaluation
6.5.1 Description of the Datasets
6.5.2 Experimental Set-up and Baselines
6.5.3 Experimental Results
6.5.4 Graph-Based Feature Selection
6.6 Conclusions and Discussion
7 concluding remarks
7.1 Summary of Contributions
7.2 Future Directions
bibliography
