Grindrod Peter, Higham Desmond J
Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK.
Department of Mathematics and Statistics , University of Strathclyde , Glasgow G1 1XH, UK.
Proc Math Phys Eng Sci. 2014 May 8;470(2165):20130835. doi: 10.1098/rspa.2013.0835.
To gain insights about dynamic networks, the dominant paradigm is to study discrete , or , as the interactions evolve. Here, we develop and test a new mathematical framework where network evolution is handled over continuous time, giving an elegant dynamical systems representation for the important concept of node centrality. The resulting system allows us to track the relative influence of each individual. This new setting is natural in many digital applications, offering both conceptual and computational advantages. The novel differential equations approach is convenient for modelling and analysis of network evolution and gives rise to an interesting application of the matrix logarithm function. From a computational perspective, it avoids the awkward up-front compromises between accuracy, efficiency and redundancy required in the prevalent discrete-time setting. Instead, we can rely on state-of-the-art ODE software, where discretization takes place adaptively in response to the prevailing system dynamics. The new centrality system generalizes the widely used Katz measure, and allows us to identify and track, at any resolution, the most influential nodes in terms of broadcasting and receiving information through time-dependent links. In addition to the classical static network notion of attenuation across edges, the new ODE also allows for attenuation over time, as information becomes stale. This allows 'running measures' to be computed, so that networks can be monitored in real time over arbitrarily long intervals. With regard to computational efficiency, we explain why it is cheaper to track good receivers of information than good broadcasters. An important consequence is that the overall broadcast activity in the network can also be monitored efficiently. We use two synthetic examples to validate the relevance of the new measures. We then illustrate the ideas on a large-scale voice call network, where key features are discovered that are not evident from snapshots or aggregates.
为了深入了解动态网络，主流范式是研究离散的，或者随着相互作用的演变而变化的情况。在这里，我们开发并测试了一个新的数学框架，其中网络演化是在连续时间内处理的，为节点中心性这一重要概念提供了一种优雅的动态系统表示。由此产生的系统使我们能够追踪每个个体的相对影响力。这种新设置在许多数字应用中是很自然的，具有概念和计算上的优势。新颖的微分方程方法便于对网络演化进行建模和分析，并产生了矩阵对数函数的一个有趣应用。从计算的角度来看，它避免了在普遍的离散时间设置中所需的在准确性、效率和冗余性之间进行的尴尬的前期折衷。相反，我们可以依赖最先进的常微分方程（ODE）软件，其中离散化是根据当前的系统动态自适应地进行的。新的中心性系统推广了广泛使用的卡茨度量，并使我们能够在任何分辨率下识别和追踪在通过随时间变化的链接广播和接收信息方面最具影响力的节点。除了经典的跨边衰减的静态网络概念之外，新的常微分方程还允许随着时间的推移进行衰减，因为信息会过时。这使得可以计算“运行度量”，从而可以在任意长的时间间隔内实时监测网络。关于计算效率，我们解释了为什么追踪信息的优秀接收者比优秀广播者成本更低。一个重要的结果是，网络中的整体广播活动也可以被有效地监测。我们使用两个合成示例来验证新度量的相关性。然后我们在一个大规模语音通话网络上阐述这些想法，在这个网络中发现了一些从快照或聚合数据中不明显的关键特征。
