Network Data File Formats

A network is a mathematical structure composed of underlying graph and data that are assigned to its nodes or links.

Formally a network is given by \({\mathcal N}\) = ( \({\mathcal V}\), \({\mathcal L}\), \({\mathcal P}\), \({\mathcal W}\)), where \({\mathcal G}\) = ( \({\mathcal V}\), \({\mathcal L}\)) is a graph, \({\mathcal V}\) is a set of nodes, and \({\mathcal L}\) = \({\mathcal A}\) ∪ \({\mathcal E}\) a set of links composed of directed links or arcs \({\mathcal A}\) and undirected links or edges \({\mathcal E}\). Their sizes are usually denoted by n = | \({\mathcal V}\)| and m = | \({\mathcal L}\)|, \({\mathcal P}\) is a set of node value functions or attributes p : \({\mathcal V}\) → A, and \({\mathcal W}\) is a set of link value functions or weights ω: \({\mathcal L}\) → B. Attributes of nodes \({\mathcal P}\) and attributes of links \({\mathcal W}\) can be measured in different (numerical, ordinal, or nominal) scales.

In computers the data are stored in files. Files are essentially sequences of bits. A file format specifies how information is organized inside the file. A Network File Format – NFF is specifically oriented towards storing network-related data.

We expose two points of view on NFFs. The first is user oriented in terms of network construction and maintenance, and the second is computer oriented in terms of computer resource requirements. Both intertwine to some extent.

The NA usually begins with data acquisition and construction of networks. To store the network data, we have to select an appropriate format. If the amount of data is small enough, the network can be constructed by hand, either in a text editor or in some spreadsheet program like MS Excel. When the amount of data is larger, but still manually acquired, we can manage it within a database. In other cases, when the data are already available in digital form, we may accede to automated processes, either directly with a suitable conversion or with network collection/construction tools or with custom program solution etc. A good example is collecting the data from the Internet.

In computer terms, a network representation depends on network size, intended usage, storage location, etc. It also depends on network density, network element attributes, additional data and desired visual properties of network, etc. For example, a space consumption and speed of reading and writing of a given format are important when we work with very large networks. At the end it is a matter of compromise between user- friendliness and the required hardware resources. While tighter, optimized formats are faster to read and require less space and processing, they are harder to read and edit by the user without special tools.

We distinguish three major groups of NFFs. Text formats focus on readability and portability. They include XML formats (Extensible Markup Language) as a subgroup. XML formats focus more on portability, adaptability, and scalability. The third group associates are binary formats. Their focus lies on performance, compactness, and optimization. However, they are unreadable by users and special software is required to handle them. Compressed formats may be considered binary as well, but they are rare. In addition to these, a database may also be considered as a format to represent networks. A network data transfer using clipboard is supported by few applications only and is meant for transfers of small amounts of the most basic network data. Moreover, many custom formats are defined as an API interface to data on various internet databases, which can be used as network data source.

Text file formats are represented as text, readable by humans. As long as their structure is known, special software is not needed to read and edit them. We only need a standard text editor. For practical reasons, these NFFs are the most popular. A subgroup of text-based formats is a group of XML-based formats. Besides advantages of text formats, XML formats are the most flexible in terms of incorporating new features. As they all follow the basic XML syntax, writing programs to handle them is simple. They are often used as an interchange format between various programs. The bad side of text-based formats is that they are more prone to errors introduced by manual editing; they require more processing power to encode/decode and take more space.

The majority of NA software supports the export and import of at least one text format, and many of them also support some form of a binary format, but binary formats are mainly proprietary and specific. The intent of binary formats is usually in smaller size and no conversion of the stored data, which results in faster reading and writing operations. A space consumption of a wasteful XML representation might be easily in the range of 10-fold increase in required space or worse in comparison to a tightly packed binary representation of the same data. As a compromise, some NA tools can read XML files directly from ZIP compressed files. Spending more on processing, space consumption can be alleviated a lot even for XML NFFs. But in general, when space becomes an issue, for instance, when dealing with huge networks, which by a definition can no longer be stored in a computer memory as a whole, a binary format provides the only practical way to manipulate them, both in terms of storage, which today could take terabytes of disk space, and in terms of processing, which is usually also much more efficient with binary formats. Binary formats are usually closely related to data representation in the computer memory. When the file content is transferred into memory, they require small amounts, if any, of computationally demanding data parsing. A bad side of binary formats is in lack of human readability. Except by using them in dedicated software tools, we cannot do much with them. They are unpractical to work with, and without a complete specification, they tend to be quite incomprehensible. They have also a very poor adaptability. Incorporating new features into binary formats, yet maintaining backward compatibility could be extremely challenging. Binary formats mainly serve as software-specific and optimized intermediate solutions. The main input and output data formats are usually text based.

Some NA applications enable users to import and export data through database connection adapters. This applies especially to corporate environments, where many users work on the same data, accessible from central database. Huge networks may be provided in this way also. These formats are actually database schemes, which describe the structure of network data stored in a database file and managed by server software providing a connection string access to client applications, for example, Advanced Visualization and Analysis (Tom Sawyer Perspectives). Although schemes of data on various databases may be different, we will group them together and refer to them simply as database format.

Some online services like Amazon, YouTube, and Google Data provide clients with an API to their data. The API is an interface, which provides a programmatic access to service database, and is usually implemented in terms of web service with a description, provided by WSDL (web service description language) or similar schema. In other words, web service description gives the description of the transfer format between server and a client. The base level data is usually exchanged in XML or alternatively in JSON format, but the inner structure is dependent on the API implementation. Both are used as exchange formats of the data, serialized into structured objects for transmission over the Internet. The user however can, in most cases, avoid learning the structure of exchange format, as a client side code can be usually generated automatically from web service descriptions. User can therefore access data in terms of function calls, without paying attention to underlying exchange format.

To represent a network in a file, we have to select a suitable representation of sets \({\mathcal V}\) and \({\mathcal L}\) in network definition. The set of nodes \({\mathcal V}\) either can be listed explicitly or is constructed implicitly from the specification of links – dispersed representation. Links (set \({\mathcal L}\)) are usually given by a set of node pairs. As a link is defined, its nodes are defined simultaneously on the fly. A problem with implicit node definition is how to specify isolated nodes as they are not encountered in any link definition. If nodes are represented with successive numbers, for example, only their number can be given in advance. Isolated nodes do not need to be defined additionally in this case. (This representation could be also treated as explicit.) An advantage of explicit definition over implicit is that if the same set of nodes is used in various sets of links (to define networks on the same set of nodes), we do not need to redefine nodes every time, especially when they have embedded attributes. Attribute embedding is described in section “GraphViz (DOT).”

Nodes are represented by their unique keys (identifiers). Identifiers can be either artificial, as successive numbers as already mentioned, or native, as node names or their attribute values, for example, as long they are distinct among all nodes. A standard approach to define links is with a sequence of pairs of their end-node identifiers. This is common in text formats, especially in XML formats as nodes are represented by XML elements, which contain identifiers. If the network contains only undirected/directed links, the order of link end nodes is insignificant/significant. If the network contains both directed and undirected links, links can be defined in two separate sections in a file (one for undirected and one for directed links). Contrary they can be defined in a single section as well, but then they have to be tagged with attributes which specify their direction. While first approach is common in text formats and less in XML formats, the second is more frequent in XML formats. Similarly as with direction attribute, links can have weight attributes assigned as well. Links can also be defined in two more compact forms. They can be specified by sequences of identifiers of nodes which lie on a path in the network.

Alternatively they can be specified by star structures, defined by identifier of a common central node followed by a list of identifiers of nodes adjacent to source node. The first approach is useful for representing links of networks, which contain many long disjoint paths, and second for more dense networks, which contain many stars – nodes with many adjacent nodes, respectively. In worst case, both approaches can degenerate into standard form. They are rarer and are hardly found in XML formats as the space consumption is usually not an issue in XML formats. Using all three approaches, nodes can be defined implicitly. Every time a link is added, the corresponding end nodes are added to the set of nodes, if not already present.

Another representation of network is by adjacency matrix. It is suitable for relatively small or very dense networks. For dense networks, a matrix representation is the most space efficient. It is essentially a list of n lists of n values. A value in j th position in i th list represents the weight of link (arc) i → j. When the network consists of edges only, a triangular matrix representation can be used, as the matrix is symmetrical. Some NFFs also allow omitting the matrix diagonal. Most text and binary NFFs support the matrix representation.

A special evolutionary network representation uses a stream of structure-changing events like adding, deleting, or changing attributes of network elements. This approach is suitable when we want to follow network dynamics. A typical example is a Graph Stream format (The DGS File Format Specification). A stream, that contains only grouped additions of nodes and grouped additions of edges where the order of elements in each group is unimportant results into two lists, a list of nodes and a list of edges. This is a common way of specifying network elements in most text formats.

The information about attributes of network’s elements either can be attached to the corresponding elements or provided in separate tables.

A nonempty subset C ⊆ \({\mathcal V}\) is called a cluster (group, class). A nonempty set of clusters C = { C _i } forms a clustering.

A clustering C = { C _i } is a partition if and only if ⋃ C = ⋃ _i C _i = \({\mathcal V}\) and for i ≠ j the corresponding clusters are disjoint C _i ⋂ C _j = ∅.

A clustering C = { C _i } is a permutation if and only if C is a partition and | C _i | = 1.

A clustering C = { C _i } is a hierarchy if and only if C _i ⋂ C _j ∈ {∅, C _i , C _j }.

A hierarchy C = { C _i } is complete if and only if ⋃ C = \({\mathcal V}\) and is basic if for all υ ∈ ⋃ C also { υ} ∈ C.

Clustering, partitions, permutations, and hierarchies can all be stored in a form of an integer vector. While values of individual cluster in clustering may not have any specific meaning, the values of elements in partition belong to clusters. In partition p [ υ] = i − vertex υ belongs to cluster C _i . In permutation p [ υ] = i − vertex υ is in the i th position. In hierarchies each element points to its parent. Root of hierarchy is usually determined with a negative value or with 0 or some other predefined value.

Temporal or dynamic networks (Batagelj 2009) are networks with time as an additional component. They change their structure and property values in time. Using temporal networks we can represent their evolution.

Temporal network \({\mathcal N}\) _T = ( \({\mathcal V}\), \({\mathcal L}\), \({\mathcal P}\), \({\mathcal W}\), \({\mathcal T}\)) is obtained if the time \({\mathcal T}\) is attached to an ordinary network. \({\mathcal T}\) is a set of time points. In temporal network nodes υ ∈ \({\mathcal V}\) and links l ∈ \({\mathcal L}\) are not necessarily present or active in all time points. If a link l ( u, υ) is active in time point t, then also its end nodes u and υ should be active in time t. The network consisting of links and nodes active in time t ∈ \({\mathcal T}\) is denoted by \({\mathcal N}\) ( t) and is called the time slice in time point t. The notion of time slice can be extended to time intervals.

In a two-mode network (Batagelj 2009) \({\mathcal N}\) = (( \({\mathcal V}\) ₁ \({\mathcal V}\) ₂), \({\mathcal L}\), \({\mathcal P}\), \({\mathcal W}\)), the set of nodes \({\mathcal V}\) = \({\mathcal V}\) ₁ ⋃ \({\mathcal V}\) ₂ consists of two disjoint sets of nodes \({\mathcal V}\) ₁ and \({\mathcal V}\) ₂, and all the links from \({\mathcal L}\) have one end node in \({\mathcal V}\) ₁ and the other in \({\mathcal V}\) ₂.

A two-mode network can also be described by a rectangular matrix \(A = {[{a_{u\upsilon }}]_{{{\cal V}_1} \times {{\cal V}_2}}}\): \({a_{u\upsilon }} = \left\{ {\matrix{ {{w_{u\upsilon }}} \hfill & {(u,\upsilon ) \in {\cal L}} \hfill \cr 0 \hfill & {(u,\upsilon ) \notin {\cal L}} \hfill \cr } } \right.\)

where w _uυ is the weight of link ( u, υ).

Examples: a network of papers × authors, businessmen × boards of directors, etc. Also the network of formats and tools supporting them in section “An Overview of NFFs and Related NA Software” is a two-mode network.

n-mode networks also exist, but they are rarely used in practice. An n-mode network can be specified using an additional partition of nodes – the mode partition.

Multiple(x) or multi-relational networks (de Nooy et al. 2012) are networks which have only one set of nodes and different sets of links on them \({\mathcal L}\) = ( \({\mathcal L}\) ₁, \({\mathcal L}\) ₂, …, \({\mathcal L}\) _r ). Examples of such networks are the following: lines of transportation system in a city (stations, bus lines), semantic networks (words, semantic relations: synonymy, antonymy, hyponymy, meronymy), etc.

A hypergraph (Berge 1989) is a generalization of a graph in which an edge can link any number of nodes. Formally, a hypergraph \({\mathcal H}\) is a pair \({\mathcal H}\) = ( \({\mathcal V}\), ℰ _h ) where \({\mathcal V}\) is a set of nodes, and \({\mathcal E}\) _h is a set of nonempty subsets of \({\mathcal V}\) called hyperedges or simply edges. Therefore, \({\mathcal E}\) _h is a subset of \( {\mathcal P(\mathcal V)}\, \backslash \, \{\emptyset\}\), where \( {\mathcal P(\mathcal V)} \) is the power set of \({\mathcal V}\). In some formats, generalized networks based on hypergraphs are supported. Hypergraphs can be represented by their incidence matrix that is essentially a two-mode network, hyperedges × nodes – we will not consider this as a NFF support for hypergraphs.

An important aspect of text formats is their ability to incorporate comments. Comments can be embedded also in binary formats, but they are specifically encoded and accessible only in compatible software. Since XML has a built-in commenting, all XML-based formats support it. Comments may appear at random places throughout the entire XML file. Comments are supported also in most plain-text formats, but their location and the way of specifying them varies. While more compact text formats allow them only, if at all, in predefined sections of a file and in a limited form (no line breaks, for instance), the extensive ones allow them in a more general form and anywhere.

A network is described by its underlying graph structure and various data structures in form of property tables, partitions, clusters, hierarchies etc. In some formats each data structure is stored in a separate file. Saving each structure in its own file is fast and allows us to keep many versions of the same, loosing minimal space. This is convenient while working on the problem, but later we tend to forget what each file is for. The approach requires the user to be well organized and keep a special documentation about his or her work. Other formats allow the user to put many networks and other complementary data together and store them into a single file. This may be practical when we want to keep our work as a whole, although saving everything into a single file might take more time. XML-based formats are the most appropriate for the task, because of their natural tree structure. An additional level (envelope) usually suffices to join content of many XML files together into a single file without much of additional effort to adapt the software to handle joint files. Another, and probably the best, option is a hybrid way, keeping advantages of single file approach and also advantages of multiple disjoint files. A project file, which joins together all the other files in an organized way, is added to the network data files. Now the user may edit separate files by hand, for instance, or modify all of them at the same time inside a dedicated analysis environment when working on the problem.

To represent a network on a picture, we usually need additional information and/or graphical arrangement of the network, the so-called layout (Batagelj 2009). Many formats provide the option to incorporate a single static layout of a network, typically in a form of arrangement and appearance of network elements, given by coordinates for every node, colors of nodes and links, shapes of nodes, etc. On the other hand, only few formats enable the user to include multiple layouts – with a style in a limited form. For example, in GraphML (The GraphML File Format) one can specify many layouts for the same network. The style defines an arbitrary number of layouts in a parametrical or even programmatic fashion. While no established format supports this kind of style definition, most of XML formats are flexible enough for a suitable extension to enable it without a need to modify the existent software.

Some networks are obtained by combining smaller subnetworks often from a fixed collection of “bricks” or by transformations replacing parts of the network with other parts (inductive classes of graphs). There also exist several decompositions of networks. The information about the composition of a network can be used in more efficient algorithms for some problems. An attempt to describe networks by their composition was made in NetML (Batagelj and Mrvar 1995).

Metadata are the data about the data which describe the main data content in some way. They help the user to manage files and may be used to optimize the flow of analysis as well. Examples are the creator or author of the network data, time and date of creation, sources of data, means of creation, legal rights, etc. Although formats may store metadata in form of comments, XML formats and some other formats provide the genuine support for metadata.

Some formats enable the user to store general network properties determined by the user or from computations. Examples are the information whether the network is planar- or scale-free, maximum degree of nodes, number of connected components, etc. The idea is to save the results of time-consuming algorithms that do not take too much space. This data can be later used to speed up other algorithms. It can be used also by search procedures in collections of networks.

One of the most popular graph (network) file interchange formats is GraphML (The GraphML File Format). It is a comprehensive and easy- to-use file format. It consists of a language core to describe the structural properties of a graph and a flexible extension mechanism to add application-specific data. Its main features include support of directed, undirected, and mixed graphs, hypergraphs, hierarchical graphs, and graphical representations, references to external data, application-specific attribute data, and lightweight parsers.

Unlike most other NFFs, GraphML is based on XML and therefore ideally suited as a common denominator for all kinds of services generating, archiving, or processing networks.

Another widely used NFF is Pajek NET format (Mrvar and Batagelj). It is text based, and since Pajek was developed for analysis of large networks, it tries to be compact yet clearly readable. The underlying graph can be described as link list, list of lists of neighbors, or adjacency matrix (Stein et al. 2009; Mehlhorn and Sanders 2008). Nodes/links may have various attributes as label, color, shape/pattern, size/width, position/value, etc. To save space the groups of successively defined nodes or links may have attributes defined only once. NET format supports two types of descriptions of temporal networks. The first description is based on time intervals of presence in which the node/link is active in network and the second on events (show edge, add node, change node property, etc.). The Pajek NET format also supports multi-relational networks, two-mode networks, p-graph representation of genealogies, and Petri nets. A line preceded by % is a comment.

UCINET DL format (Borgatti et al. 2002) is the most common file format used by UCINET software. It is text based and is defined by three main sub-formats:

This format is more compact than link list as source node in every line is given only once.

Frequently used NFF is the representation of network by its adjacency matrix (Stein et al. 2009; Mehlhorn and Sanders 2008). Each matrix row is represented as a line of its values separated by spaces, tabulators, or some other delimiter (comma or semicolon in CSV – comma separated values). Using some additional information, provided by a user, .TXT or .CSV adjacency matrix files may contain alternating rows and/or columns of link attributes and header rows/columns of node attributes. The main advantage of this format over other formats is in its simplicity and efficiency for dense networks. It is not appropriate for large sparse networks as it requires too much space.

It is the simplest NFF, also popular in many NA applications. A network is represented by a list of links – which are in separate rows described by pairs of their end nodes represented by their indices or names. Graph nodes are often specified implicitly. Link attributes can simply be added at the end of the row. Node attributes can also be defined but only if nodes are specified explicitly in a separate list. The user has to provide some additional information in this case. The simplicity of the format is its main benefit.

There are many different programs that work with graphs and networks, but almost all of them use their own file format. As a consequence, exchanging networks between different programs requires conversion. Simple tasks like exchange of data, externally reproducible results, or a common benchmark suite are much harder than necessary. GML was developed to overcome these problems. It supports attaching arbitrary information to graphs, nodes, and edges and is therefore able to emulate almost any other format.

DOT (Graphviz) is a plain-text graph description language. It is a simple way of describing graphs that both humans and computer programs can use. Main features of DOT language are undirected and directed graphs which may have arbitrary node and link attributes. Attributes are embedded after each node’s id. For example, link a − b, where node b should have attribute color equal to blue, can be specified as a − c[ color = blue]. Using attributes one can also define a visual layout. Single line and multiline commenting is supported.

A distinct feature of DOT language is the ability to specify links in a more compact way than with a more common adjacency list (Stein et al. 2009; Mehlhorn and Sanders 2008) approach. For example, lines a − b and b − c between nodes a, b, and c can be specified by a single string a − b − c. At the same time definition of nodes is accomplished.

NA tools, especially visually oriented, enable the user to export snapshots of the network in a form of an image. Images are often treated as the end product of the analysis and show the resulting network in the most informative way. Images however cannot be (easily) translated back into the original network automatically. We distinguish two major groups of image formats. The first is a group of raster image formats, where image is represented by a matrix of pixels. The second group consists of vector formats, where predefined parameterized graphical elements are used to construct the image, e.g., circle, line, polygon, and spline. While raster formats are good for complex, dispersed, blurred, and photography-like representations, vector formats are useful for sharp, crisp, and more detailed representations. From the user point of view, the major difference between raster and vector images is in resolution. It is fixed for raster images and is arbitrary for vector images. Common examples of raster formats are portable network graphics, PNG; Joint Photographic Experts Group, JPEG; bitmap, BMP; tagged image file format, TIFF; etc. Examples of vector-based images are scalable vector graphics, SVG; encapsulated postscript, EPS; postscript, PS format; etc. Some vector formats may also contain raster elements. For example, SVG can link external raster images with vector- based graphics. The vector formats that allow embedding of raster and vector elements in a single file are the portable network document, PDF; CorelDraw documents, CDR; Adobe Illustrator documents, AI; etc.

Some visually oriented NA tools provide the export of networks into 3D models. Molecules as networks are a good example where it is convenient to export them in 3D. In comparison to 2D network representations, 3D models of networks are almost universally vector based. Well-known 3D formats are 3D version of scalable vector graphics, SVG; virtual reality markup language, VRML and its successor X3D; AutoCAD, DXF; 3D Studio, 3DS; and others. In chemistry and biology Kinemages, KIN, and MDL Molfile are more popular.

We will try to answer the following question: “Is it possible to transform a given format into another one using any of existing tools?” In Fig. 3 the matrix of a subset of 56 out of 86 network formats from Fig. 1 is displayed. These 56 formats are all convertible into one another using tools from Fig. 1. Among 30 excluded formats are two pairs of mutually convertible proprietary formats of m Draw and Mind Manager and the 26 remaining formats that cannot be mutually converted into any other format. From the matrix in Fig. 3, we can see that the majority of file formats can be converted one into another in at most two steps. Except few exceptions, all formats can be transformed in three steps. Under the assumption that we have an access to all tools, it is relatively easy to convert almost any format into a desired format. But attention, some conversions are only partial. Certain formats are more general than others and conversion to a more specialized format may omit some data. For instance, the conversion from GEDCOM or from Molecule MOL format into Pajek NET format is complete (with respect to graph structure), whereas the opposite is not the case (not every network can be represented as genealogy or as molecule). This could be the reason why a unified converter, able to perform the majority of conversions, does not exist (Fig. 3).