Structural Constraints on the Mixing Patterns of Binary Node Metadata

Assortative mixing is the tendency of nodes with a common attribute (also referred to node metadata) to be connected to each other in a network. It is typically measured using Newman’s assortativity coefficient [1], which is the network analogue of Pearson’s correlation. Just as correlation plays an important role in identifying relationships between pairs of variables, assortativity plays a fundamental role in understanding how a network is organised with respect to a given attribute of the nodes. The assortativity coefficient for a categorical node attribute measures the proportion of links in the network that connect nodes with the same attribute value relative to the expected proportion of links under a null model. Similar to Pearson’s correlation, assortativity is constrained to lie in the range r∈[-1,1], however the structure of the network places further constraints that often make the maximum and minimum values unattainable. These constraints introduce issues when we try to interpret values of assortativity, as r is no longer the proportion of the maximum value relative to the expected value.

Here we consider the case of binary metadata, e.g. gender of actors in a social network, and we investigate how different constraints affect the range of permissible values of assortativity. These constraints are imposed by maintaining different characteristics of the network structure (specific degree sequence or specific graph topology) and node metadata (proportion of nodes per category or specific assignment of categories to nodes). Thus, by combining both types of constraints, we consider three different spaces of assortativity (omitting the fourth combination as it corresponds to a single configuration): the metadata-graph space (mgs), the graph space (gs) and the metadata space (ms). Figure 1 illustrates qualitatively the relationship of the bounds of each of these spaces. These bounds can be substantially far from -1 and 1.

Matteo Cinelli, Leto Peel, Antonio Iovanella and Jean-Charles Delvenne
Monday, September 24, 2018 - 11:30 to 11:45


The official Hotel of the Conference is
Makedonia Palace.

Conference Organiser: NBEvents

The official travel agency of the Conference is: Air Maritime

Photo of Thessaloniki seafront courtesy of Juli Bellou
fb flickr flickr