3 Key excerpts on "Graph Data Structure"

• 

  eBook - ePub

  Bioinformatics Algorithms

  Design and Implementation in Python

  • Miguel Rocha, Pedro G. Ferreira(Authors)
  • 2018(Publication Date)
  • Academic Press

    (Publisher)

  Chapter 13

  Graphs: Concepts and Algorithms

  Abstract

  In this chapter, we present the mathematical concept of graph and its computational representation. We address some of the main algorithms over graphs and develop a set of Python classes to implement different types of graphs and underlying algorithms. Graphs will be central in the development of algorithms for handling biological networks and genome assembly, tasks addressed in the next chapters.

  Keywords

  Graphs; Graph representations; Adjacency lists; Node degree; Paths and distances in graphs; Graph search algorithms

  In this chapter, we present the mathematical concept of graph and its computational representation. We address some of the main algorithms over graphs and develop a set of Python classes to implement different types of graphs and underlying algorithms. Graphs will be central in the development of algorithms for handling biological networks and genome assembly, tasks addressed in the next chapters.

  13.1 Graphs: Definitions and Representations

  A graph can be defined, in Mathematics, as a set of objects in which some of the pairs of the objects in this set are related. While they can be easily defined and have a simple structure, they are powerful and flexible data structures, with a huge set of applications in computer science and many fields of science and engineering.

  Formally, a graph G can be defined by two sets:

  ( V , E )

  , where V is the set of objects, named as vertices or nodes of the graph, and E is a set of pairs

  ( u . v )

  of vertices from V, named edges or arcs, indicating the existence of a relationship between u and v.

  The edges in E may have an orientation, i.e. the pairs are ordered, in which case the graph is classified as directed, or digraph. Otherwise, the pairs are unordered and the graph is termed undirected

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Culture, Curiosity and Communication in Scientific Discovery

  The Eye in Ideas

  • Nigel Sanitt(Author)
  • 2018(Publication Date)
  • Routledge

    (Publisher)

  6

  Graph theory

  Up to now I have described the network model for scientific theorizing in qualitative terms. There is, however, a branch of mathematics which deals with networks at a quantitative level called graph theory . There is an enormous range of types of networks and graph theory provides a mathematical and formal framework for describing, analysing and calculating with networks.

  All the procedures and characteristics of networks, which I have described, have a ready interpretation in graph theory and many results and theorems in graph theory have a corresponding application in the network model I have proposed.

  There are no true propositions in science but mathematics is an effective tool both as cement within scientific theories, linking assumptions and predictions, and as a logical foundation for the network structures that constitute the backbone of our understanding.

  6.1 What is a graph?

  There are two different meanings of graph , which have arisen rather confusingly in mathematics. The more commonly known meaning of graph refers to a data plot. The usual example of this type of graph is the familiar diagram of Cartesian coordinates, which consists of two perpendicular axes designated x (horizontal) and y (upright). There are many kinds of graph other than the Cartesian coordinate graph, which was described by René Descartes in 1637.

  The second meaning of graph , and the one relevant to the present work, was first proposed by the Swiss mathematician Leonhard Euler in 1735. In this sense of the word, a graph is a collection of objects linked together. Pictorially, they are represented by nodes, which may or may not be linked together by lines.1

  If the links are ordered then the lines have arrows on them and are referred to as arcs and the nodes are called vertices; such a graph is said to be directed. Figures 5.1 and 5.2 in the previous chapter are examples of directed graphs or digraphs.

  The vertices or nodes of a graph may be labelled or unlabelled. In the case of a graph, the degree of a node is the number of lines or edges which join the node to other nodes. For a directed graph, because arrows on arcs can be in to or out of a vertex, we need to define two quantities for each vertex: the in-degree and the out-degree. A vertex in a digraph with in-degree zero is called a source, and one with out-degree zero is called a sink.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Analyzing Social Networks

  • Stephen P Borgatti, Martin G Everett, Jeffrey C Johnson(Authors)
  • 2018(Publication Date)
  • SAGE Publications Ltd

    (Publisher)

  v. When two vertices are joined by an edge, we say the vertices are adjacent. So, adjacent just means ‘has a tie’. If an edge connects A with B, and another edge connects A with C, we say that the two edges are incident upon A. The number of edges incident on a node is called the ‘degree’ of that node.

  Graphs may be directed or undirected. In a directed graph, the edges are like arrows – they have direction. Edges in directed graphs are often referred to as arcs, and can be thought of as ordered pairs of vertices. For example, the graph depicted visually in Figure 2.1 consists of a set of vertices V = {A, B, C, D, E}, and a set of ordered pairs E = {(A, B), (B, C), (C, D), (D, A), (D, E)}. The (C, D) pair indicates that C sends a tie to D. If the tie is reciprocated, the pair (D, C) would also be a member of the set E (but, in the example, it is not). Directed graphs are used to represent relational phenomena that logically have a sense of direction – for example, ‘is the parent of’ and ‘gives advice to’. Note that directed relations can be reciprocated. It could be, for example, that in a certain group of people, every time someone gives advice to someone else, they receive advice from that person as well.

  In undirected graphs, the edges are unordered pairs. Undirected graphs are used for relations where direction does not make sense or logically must always be reciprocated, as in ‘was seen with’ or ‘is kin to’.

  Although not a mathematical necessity, in social network analysis we usually organize things such that every edge in a graph means the same thing – that is, represents the same social relation. So a given graph G(V, E) contains only friendship ties, while another graph H(V, A) contains only advice ties among the same set of vertices. This means we think of the friendship and advice networks as different from each other and analyze them separately, though there are certainly exceptions to this.1

  Sign up to read

  Learn more about book