D ATA AND C ONCEPTS

Each network node is associated with a state and a loading. The state and loading values are both assumed to be observed without measurement uncertainty. In general, node state data can be either discrete- or continuous-valued, but here only binary node states are considered in detail.

Respectively, loading data may assume either discrete or continuous values. Here the state of node as a random variable is denoted as , whereas its value in a network observation is

denoted as . Similarly, the loading of node in a network observation is denoted as . The network observation of a set of node state–load pairs is denoted as , . The number of network nodes is denoted by and the number of observations by .

Each node may also have a specified physical location and always has a set of neighbours—

MTNs assume both of these pieces of topology information. Here nodes are also assumed ho-mogeneous in the sense that they are structurally identical. Both the physical locations of nodes and their neighbourhood relations are assumed constant through network observations. The physical location of node , if given, is described by the node location map of the network and is denoted by a coordinate vector . The neighbours of node are denoted by a set of nodes

, which for all nodes can be visually presented as a graph.

Specifying a network node with a state and loading in general description means that for some specific networks, such as GSM networks, the information available about the nodes for each node must be compressed into the two variables, the state and the loading. With GSM networks, the two variables have the following meaning: the node state variable describes the performance of a BTS cell, e.g., how well the cell node performs requests from mobile stations; respectively, the load variable describes the external load, the amount of traffic caused by speech and data flows to and from mobile stations and affecting the BTS cells. However, since this is not the only way to define node states and loads in a GSM network, one goal in seeking an appropriate net-work model is also to find an appropriate node description.

Structure, or topology, is essential in defining many properties of a networked system [9], [44], [143]. Topology refers here to the list of nodes in networks and the list of interconnections be-tween the nodes. In addition, the term graph, or graph structure, is used here in parallel to topol-ogy. For a comprehensive specification of a networked system, the weights or strengths of inter-connections are often specified in addition to a topological or graph description.

3.2 Topologies

Even diverse networks may share a similar basic structure of network topology. Only few such structures have been thoroughly studied in graph theory [38]. Regular networks are usually a sim-plification, or an idealisation, of a true system topology. Yet regular topology structures exist in nature as well; e.g., in ice crystals, where the atoms are organised in a three-dimensional regular square grid. In a two-dimensional lattice, regular networks may assume interconnections in squares, triangles, or hexagonals (a regular square lattice structure is shown in Figure 3.1). In regular networks, if the network is infinite, each node has the same number of neighbours. In finite regular networks, the edge-nodes have fewer neighbours than the other nodes. However, in some cases, finite networks are deemed to have periodic boundary conditions with all nodes hav-ing the same number of neighbours. Periodic boundary conditions mean that the edge nodes are neighbours to nodes at the edges on the opposite side of the network, the network being a torus.

Random graphs, or random networks, [47], [48], [133] are models for network structures where node links are drawn samples according to some specified random process [9]. Widely studied

[47], [48], the Poisson process leads to the Poisson distribution of the number of neighbours, but random graphs with arbitrary distributions of the number of neighbours have been studied as well [101], [102], [107] (a random network topology is shown in Figure 3.1). Because the Poisson distribution is right-skewed with exponential tails, only few nodes have many more neighbours than the typical neighbourhood. Though extensively used to study the properties of real net-works, random graphs with the Poisson distributed number of neighbours are seldom realistic since the real distribution of the number of neighbours is usually non-Poisson, such as the power law or exponential distribution [9], [25].

Scale-free networks [9] are more complex in structure than the above with properties similar to those of many real-world networks. Scale-free networks have their number of neighbours dis-tributed according to the power law. Consequently, scale-free networks are scale invariant [9]—

their topology appears similar at all length scales. Because the power law distribution has a heav-ier tail than the exponential distribution, many nodes have relatively many neighbours (a scale-free network is shown in Figure 3.1). An artificial generation of scale-scale-free networks (see, e.g., [9]) mimics the evolution of growing networks; i.e., a new node is more likely to connect to a node with a high than a low number of neighbours. Growing networks often self-organise into scale-free structures [44].

Two further properties are generally used to classify network structures. One is the mean-shortest path length (MSPL), which is the average node graph distance over all node pairs. Graph distance means here the smallest number of steps between two nodes along neighbourhood rela-tions. Such networks have short graph distances in comparison to the size of the network. The other is about the clustering of the network structure, characterised by the clustering coefficient [160], i.e., how close the nodes are on average to forming cliques with their neighbours. Clique means a group of nodes in which each node is directly connected to every other node.

A network is called a small-world network if it has a small MSPL value and a large clustering co-efficient. Hence, small-world networks contain shortcut links that connect otherwise distant parts of the network, and the nodes form clusters of inter-connected node groups. Regular networks lack shortcuts and have thus large MSPL values, whereas both random graphs and scale-free networks assume shortcuts and thus small MSPL values [9]. In addition, scale-free networks and regular networks are typically highly clustered [9], whereas random networks are not because of

Figure 3.1. Examples of regular square lattice (5 5) (left), random network (middle), and scale-free network (right).

The last two topologies have both 32 nodes and 32 links and are redrawn according to [26].

their randomly drawn links [41], [9]. Among regular networks, only nodes in triangular networks form cliques with their neighbours and assume thus a non-zero clustering coefficient. Finally, true networks often have some special properties that go beyond generated idealised topologies, and finite networks may be hard to classify as pure members of any topology types.