Network and Sparse Matrix Representation

A sparse matrix is a matrix in which most of the values are zero. The ratio of zero values to non-zero values is known as the sparsity. An estimation of a matrix's sparsity can be helpful when creating hypotheses about the availability of networks. Extensive big sparse matrices are commonly used in machine learning and natural language parsing. It is computationally costly to work with them. Recommendation engines use them for representing products inside a catalog. Computer vision uses sparse matrices and network data structures when working with pictures that contain sections with dark pixels. Network and sparse matrix data structures are also used in social graphs and map layouts. In this chapter, we will cover the following topics:

• Network representations using graphs:
  • Social network representation
  • Map layouts
  • Knowledge graphs...

Technical requirements

Install Go version 1.10 from https://golang.org/doc/install for your OS.

The GitHub URL for the code in this chapter is as follows: https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/Chapter09.

Network representation using graphs

A graph is a representation of a set of objects that's connected by links. The links connect vertices, which are points. The basic operations on a graph are the addition and removal of links and vertices. These are some different types of graphs:

• Directed graph
• Non-directed graph
• Connected graph
• Non-connected graph
• Simple graph
• Multi-graph

An adjacency list consists of adjacent vertices of a graph that have objects or records. An adjacency matrix consists of source and destination vertices. An incidence matrix is a two-dimensional Boolean matrix. The matrix has rows of vertices and columns that represent the links (edges).

Network representation using a graph is shown in the following code. A social graph consists of an array of links:

///main package has examples shown
// in Go Data Structures and algorithms book
package main

// importing...

Sparse matrix representation using a list of lists

A sparse matrix is a two-dimensional list of m rows and n columns. The shape of a matrix is m x n if it consists of m rows and n columns. Sparse matrices are used for solving large-scale problems that do not require dense matrices. For example, partial differential equations are solved by using the finite element method (FEM). Tuples of a sparse matrix are non-zero elements of the matrix.

In the following code, a sparse matrix is modeled as a list of lists. A sparse matrix consists of cells that are a list of lists. Each cell has properties such as Row, Column, and Value:

///main package has examples shown
// in Go Data Structures and algorithms book
package main

// importing fmt package
import (
  "fmt"
)

//List of List
type LOL struct {
  Row int
  Column int
  Value float64
}

The next section talks about the SparseMatrix class...

Summary

This chapter covered how to present networks and sparse matrices using graphs and a list of lists, respectively. Social network representation, map layouts, and knowledge graphs were discussed in detail with code examples. The different sparse matrix methods were also implemented with the appropriate code.

In the next chapter, algorithms such as garbage collection, cache management, and space allocation will be presented with code examples and an efficiency analysis.

Questions

• What data structure is used to represent a set of linked objects?
• What is a two-dimensional matrix with Boolean values called?
• Give a code example for a network representation using a graph.
• Which metrics can be calculated from a social graph?
• What is a cartographic design?
• Give an example of a knowledge graph and define the class, slots, and facets.
• What are the applications of sparse matrices?
• Define a list of lists and write a code sample.
• What is a map layout?
• What different operations can be performed using graphs?

Further reading

The following books are recommended if you want to know more about graphs and list of lists:

• Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
• Introduction to Algorithms – Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Data structures and Algorithms: An Easy Introduction, by Rudolph Russell