Abstract
A graph or a network is an abstract representation of a set of objects where some pairs are connected by links. Graph analytics is the systematic computational analysis of graphs/networks. In contrast to tabular data analysis, graph analytics requires a different set of tools, techniques, and algorithms tuned towards representation of the graph structure. With increasingly complex phenomena in today's world such as systems biology, epidemics, social networks, organizational collusions, international trade relationships, and internet of things, the importance of modeling such networked systems is more than ever. Therefore, graph analytics is a necessary toolkit in data science and machine learning warranting exclusive research enquiry and pedagogy. This article introduces the reader to the breadth of analytics tools, techniques, algorithms, and software. After reading this article, the reader should be able to identify problems that can use a network approach as well as develop corresponding graph-based analytics solutions.
TopBackground
A graph or a network is made up of vertices and edges. It is mathematically represented as G(V,E), where V is the set of vertices and E is the edges. In converse, vertices and edges of a graph G may be represented as V(G) and E(G) respectively. An edge joins two vertices in a graph. Likewise, two vertices are said to be adjacent if and only if there is an edge between them. Two vertices are said to be connected if there is a path from one to the other via any number of edges.
A vertex or a node is a single connection point in a graph. Vertices or nodes are entities such as people, products, biological cells, organizations which could be interconnected to each other in a particular configuration and the collection of such entities, and their interconnections constitutes the graph. Nodes are usually labeled but they could be unlabeled as well. An edge, link or relationship is a line segment that connects two nodes. A node without edges is permitted. However, an edge without nodes is not. Edges may have labels as well but are usually unlabeled. Nodes as well as edges can have their own attributes or properties.
Key Terms in this Chapter
Graph Embedding: A transformation procedure of converting nodes, edges, and graph into a set of multidimensional vectors that optimally capture the characteristics graph structure.
Graph Database: An operational database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data instead of the traditional relational/tabular structure.
Knowledge Graph: A knowledge graph is a directed labeled graph real-world entities – objects, events, situations, or concepts created and managed to construct a comprehensive view of the underlying entities, labels, and their inter-relationships.
Graph Mining: The process of algorithmically extracting patterns of interest from graphs that describe the underlying generative process or scientific phenomenon.
Network Science: A field involved with investigating the topology of complex networks using graph theory to better understand the behavior, functioning and properties of the underlying phenomenon related to the generation of the network.
Statistical Graph Model: A model that represents a network using available input features similar to how a regression model represents the relationship between inputs and outputs in a tabular dataset. It is not to be confused with graphical model which focus on representing the conditional dependence between random variables.
Exploratory Graph Analysis: Exploratory graph analysis is a collection of graph mining techniques including network visualization and summarization of network properties that are useful for initial exploration of a graph as well as feature engineering.
Social Network Analysis: The process of investigating social structures through the use of graph analytics. The nodes of the social networks are typically assumed to be individuals and the edges are based on the underlying inter-individual interaction phenomenon that is being studied such as friendship or location proximity.
Graph Analytics: Systematic computational analysis of graph data.