The interdependence of critical infrastructures, particularly of information and telecommunication networks and systems and electrical power networks has been studied intensively employing a number of different methods ranging from semi-qualitative Leontief models via percolation models and related approaches from statistical physics to agent and graph-theoretical models. In this paper we focus on the latter approach and study the structures arising from incomplete joining of two power-law networks. Both ICT and power networks are artificial networks, but a number of studies demonstrate that such networks generally exhibit scale-free properties and can be described with high accuracy by power-law degree sequence graphs. A well-known result is that the robustness of such networks to random failures and intentional attack differs considerably, with high levels of vulnerability to targeted attacks. However, differences in robustness exist based on the exact degree sequence.
Dependencies between two or more such networks can result in both dependency paths, where the length of paths and the existence of vertex-and edge-disjoint paths can inform mitigation mechanisms; more importantly, however, cycles arising indicate the existence of interdependencies that may be more difficult to recover from or mitigate. This has been studied previously for both simple graphs and for flows; however, we argue that particularly for the case of (inter-)dependencies between power and ICT networks in smart grid environments, this relation between the graphs is itself not static. We consider the existence, addition, or removal of dependencies in the form of sparse random graphs resulting in the creation of interdependence cycles. The diameter of such cycles can serve as a strong indicator of the vulnerability of the overall network as it is indicative of the attack surface of the network. The introduction of additional edges in the graph, indicating information flows in the smart grid, can- hence reduce vulnerabilities, hence the efficient discovery of such structures for a given graph is of particular interest.