Sunday, June 5, 2016

Note 3: What is actually the differece between a graph and a complex network?

A graph is a mathematical structure that is composed of a set of
elements and a relation defined on that set. It does not know about
the set of real-world entities and their relationship it
(might) represent. It is important to note that a graph does,
of course, not need to represent any real-world situation.
The 'complex network' defines the relationship between
the set of entities in the real-world and their representation
in the graph.This figure is under CC:BY with a
reference to Prof. Dr. Katharina A. Zweig or to this blogpost.
When I started to do network analysis, I was confused by the terms 'graph' and 'complex network', and I wondered whether they can be used totally interchangeably or not.

"Note 3. What is the difference between a (complex) network and a graph? The quick answer is that a graph is the abstract representation of a relation between entities while a network combines the graph with additional information about the entities and their relationship represented by the graph."

A graph is, mathematically, just the combination of any set of elements V and a relation E defined on it. A relation is just a subset of all the possible pairs of elements in the set. By definition, these pairs have an order, i.e., it makes a difference whether the pair $(x,y)$ or the air $(y,x)$ is included. If for all pairs both directions are included in the relation, we speak of a symmetric relation. If there is at least one pair that is only included in one direction, it is an asymmetric relation. The elements of the relation are called edges, when they are part of a graph, and the elements of V are called nodes or vertices.
A graph can be associated with functions, that assign values to nodes or edges. You see, on this mathematical level, everything is pretty abstract.

A complex network fills these things with meaning: the nodes suddenly represents a set of real-world entities, e.g., persons. The edges represent a relationship between the nodes. The mathematical property of the relation called 'symmetry' suddenly represents an undirected relationship, while an asymmetric relation represents a directed relationship. Functions associated with the edges are weights that capture an important aspect of the relationship, and functions associated with the nodes capture important properties of the nodes.

In most network analytic publications, you will see an identification of the nodes with their entities and the edges with the relationship they represent. This is in most cases unproblematic and saves a lot of text. Instead of writing "Two nodes are connected by an edge if the corresponding street corners are connected by a street", it is much faster to write: "In the network, street corners are the nodes and streets are the edges.".

However, such a formulation also indicates there would be a clear one-to-one-mapping. As will be seen in later blog posts, this is almost never the case: there are multiple modeling decisions to be made to come from a heap of raw data to a network representation. Here is how Brandes et al. phrase the problem in their editorial of the first issue of their journal "Network Science":

"As representation is usually defined via an isomorphism, i.e., a one-to-one mapping
between structures preserving relations, a phenomenon cannot be represented
directly but needs to be conceptualized first.
Of course, this is by no means an unusual division in science or other areas of
knowledge. Possibly because of the graphic and metaphoric connotations of the
term network, the implications of a preceding abstraction step are often overlooked
or blurred. Sometimes this may be on purpose for terminological convenience.
More often, there appears to be a lack of awareness. We feel, however, that this
distinction is crucially important for serious applications of network science to the
understanding of substantive phenomena as it points to the delicacy of interpreting
the results of network data analysis.
Interpretation essentially reverses the process of abstraction and representation
to get back to the phenomenon so that substantive theory is required to secure
Defining the isomorphism between the elements in the real-world and their counterpart in the graph is a step that is often also called operationalization and later blog post will have a lot to say about this step.

In summary: there is an important distinction between a complex network and the graph it contains. And at least in the description of how the real-world phenomenon is turned into a network representation, it is good practice to differentiate between the two different layers---the real-world and the graph representation of it. In later parts of the text, however, it might be cumbersome to differentiate between the elements of the graph and the real-world entities they represent.


(Brandes2013) Brandes, U.; Robins, G.; McCranie, A. & Wasserman, S.: "What is Network Science?", Network Science, 2013, 1, Editorial
(Zweig2016) Katharina A. Zweig: Network Analysis Literacy, ISBN 978-3-7091-0740-9, Springer Vienna, publication expected Dec 2016 

No comments:

Post a Comment