Introduction to Graphs

What is a graph? What are the components of graphs? Where do we see them in real life?

Graphs in Everyday Life

Our world is composed of countless objects and connections which we can call as physical networks like roads, phone lines, electrical wires, veins and arteries of our bodies... Besides these physical networks, we also have virtual networks like social media, Web, or the internet itself! To make it more clear here is several examples of networks from everyday life:

• The Web is a very large network whose components connect with hyperlinks
• The molecules are in the form of a network with atoms and the bonds between these atoms
• Epidemics and evolutionary trees can be modeled using networks
• Social media forms a network with different components like friends and companies that are linked together with some relations such as friendships, followers, likes or connections.

This connected data is mostly represented with graph structures in Computer Science. Throughout this post, I will be using the graph and network keywords interchangeably and social networks will be my main focus.

Understanding the Concepts

Before going into details, let us define some concepts regarding networks:

• Vertices/Nodes correspond to objects in a network
• Edges are the links between objects belonging to a network
• A graph is a collection of vertices and edges that represents relationships
• Edges of a graph might have weights indicating the strength of that link between vertices
• Graph theory is the study of graphs and their properties and a graph data structure has two basic elements: vertices and edges. We use the notation of G(V, E) meaning that the “Graph G with vertex set V and edge set E”.

If we consider an online social network as a graph, users can be represented with vertices whereas edges denote friendship relations between them. Here is a social network where the members Alice, Bob, Jack, and Jane are the four vertices of this social network and the edges between any two members corresponding to a friendship between these members.

Figure 1: Friends on a social network

• Undirected graphs have edges that do not have a direction. With undirected graphs, we can represent two-way relationships so an edge can be traversed in both directions.
• Directed graphs (Digraphs) have edges with direction. With directed graphs, we can represent one-way relationships so an edge can be traversed in a single direction.

In some cases we need directions in graphs, for instance, a directed graph needs to be used in Twitter since the relation between any user can be one-sided and you don’t need to follow each of your followers as can be seen in Figure 2. On the other hand, an undirected graph needs to be used on Facebook since both users have to befriend each other in order to actualize a friendship as in Figure 1.

Figure 2: Followers on a social network

Additionally, some attributes or features can be incorporated into nodes or edges of graphs. For instance, an individual user on a social media network might have an age property or an edge defining the friendship might have a starting date.

Types of Graphs

Graph nodes and edges might have types. A graph with a single type of node and single type of edge is called a homogeneous graph. For instance, a social network with nodes representing users and edges representing friendship constitutes a homogeneous graph (See Figure 3).

Figure 3: A homogeneous graph with 1 type of node and edge

Likewise, a graph with two or more types of nodes or edges is called a heterogeneous graph. For instance, a social network with nodes representing accounts of people, company owners, and animals; edges representing friends, co-workers, followers, and employees constitute a heterogeneous graph (See Figure 4).

Figure 4: A heterogeneous graph with 3 types of vertices and 4 types of edges

Graph Problems

Once we model data with a graph, we can define different types of problems on the graph. Here we list the most prominent ones:

• Graph classification tries to discriminate between graphs of different classes.

Figure 5: Predict whether a tumor is malignant or benign

• Community detection tries to infer communities or clusters of nodes based on the similarity of node attributes.

Figure 6: Segmentation of users into communities based on their hobbies

• Link prediction tries to infer missing relationships between entities.

Figure 7: Product recommendation from an e-commerce website

• Node classification tries to discriminate between nodes of different classes given the attributes of other nodes in the network.

Figure 8: Predicting the music preferences of a user by her friendship network

All in all…

Based on a study that Facebook conducted in 2016, any Facebook user can reach anyone else on Facebook through at most 3.57 hops. Today, everyone is somehow connected with everyone and everything by a kind of interaction. These interactions can reside in social networks, travel networks or the internet itself. To represent these connections in computers, we use graphs.

Later on, we will be going into details of how these graphs are used in different applications and I hope this gentle introduction can give you an intuition about what the graphs are and where do we see them in our everyday lives. See you on the next post!

References and further readings:

• Graph Theory
• Tsuda, K., & Saigo, H. (2010). Graph Classification appears as a chapter in Managing and Mining Graph Data.
• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics reports, 659, 1–44.
• Bhagat, S., Cormode, G., & Muthukrishnan, S. (2011). Node classification in social networks. In Social network data analytics (pp. 115–148). Springer, Boston, MA.
• Wang, P., Xu, B., Wu, Y., & Zhou, X. (2015). Link prediction in social networks: the state-of-the-art. Science China Information Sciences, 58(1), 1–38.
• Drawings are created using Sketch.io.