Modelling Negative Correlation in Complex Networks Via Anti-Transitivity

Negative correlation appears often in complex networks. For example, in social networks, negative correlation corresponds to rivalry between agents in the network, while in stock market graphs, negative correlation corresponds stocks that move in opposite directions in price action. We present a simplified, deterministic model of negative correlation in networks based on the principle of anti-transitivity: a non-friend of a non-friend is a friend. In the Iterated Local Anti-Transitivity (ILAT) model, for every node u in a given time-step, we add an anti-clone node that is adjacent to the complement of the closed neighborhood of u. We prove that graphs generated by the ILAT model satisfy several properties observed in complex networks, such as high density and densification power laws, constant diameter, and high local clustering. We also prove that the domination and cop numbers of graphs generated by the ILAT model are bounded above by small, absolute constants as time increases.