Mixing Patterns - Mixing Based On Discrete Characteristics

Mixing Based On Discrete Characteristics

Discrete characteristics of a node are categorical, nominal, or enumerative, and often qualitative. For instance, race, gender, and sexual orientation are commonly-examined discrete characteristics.

To measure the mixing of a network on discrete characteristics, Newman defines a quantity to be the fraction of edges in a network that connect nodes of type i to type j (see Fig. 1). On an undirected network this quantity is symmetric in its indices, while on directed ones it may be asymmetric. It satisfies the sum rules

,

where and are the fractions of each type of an edge's end that is attached to nodes of type . On undirected graphs, where there is no physical distinction between the ends of a link, i.e. the ends of adges are all of the same type, .

Then, an assortativity coefficient, a measure of the similarity's or dissimilarity's strength between two nodes on a set of discrete characteristics may be defined as:

with

This formula yields when there's no assortative mixing, since in that case, and when the network is perfectly assortative. If the network is perfectly disassortative, i.e. every link connects two nodes of different types, then, which lies in general in the range . This range for implies that a perfectly disassortative network is normally closer to a randomly mixed network than a perfectly assortative one is. When there are several different types of nodes, then random mixing will most often pair unlike nodes, so that the network appears to be mostly disassortative. Therefore, it is appropriate that the value for a random network should be closer to that for the perfectly disassortative network than for the perfectly assortative one.

The method of generating functions is based on the idea of figuring out the proper generating function for the distributions of our interest every time, and extract data related to the networks structure by differentiating them. Assuming that the degree distribution for nodes of type and the value of the matrix (and hence, the values of and ) are known, then we may consider the ensemble of all graphs with the specified and to yield collective (macroscopic) network characteristics. In principle, the generating function for and its first moment are given by, and, where the node of type ( in the number) and the mean degree for nodes of this type. Now we focus on the distributions that we're interested for.

The distribution of the total number of nodes reachable by following an edge that arrives at a node of type has a generating function . Similarly, the distribution of the number of nodes reachable from a randomly chosen node of type is generated by . Now we are in position to yield some of the network's properties. The mean number of nodes reachable from a node of type is

Furthermore, if is the probability for a node of type (reached by following a randomly chosen link in the graph) not to belong to the giant cluster, then the overall fraction of nodes that compose this cluster is given by

The numerical simulations based on Monte Carlo techniques seem to agree with the analytical results yielded by the formulas described above.