In the thesis we describe a new algebraic approach to the temporal network analysis based on the notion of temporal quantities. We define semirings for the analysis of temporal networks with zero latency and zero waiting time and semirings for the analysis of temporal networks where the latency is given. For temporal networks with zero latency and zero waiting time we present algorithms for the efficient operations with temporal quantities and for the computation of chosen centrality measures that are generalized cases of centrality measures for static networks. We describe the computation of degree, clustering coefficients, closeness, betweenness and recursive measures of centrality. We explain the eigenvector centrality, the Katz centrality measure, the Bonacich ▫$\alpha$▫ and ▫$(\alpha,\beta)$▫ centralities, the HITS (hubs and authorities) centrality, and the pageRank centrality. We define activity and attraction coefficients in temporal networks. Centrality measures allow us to identify groups of important vertices. With a review / comparison of the vertices from the groups we get an insight into their roles through time. We present the algorithm for computing the closure of a temporal network over an absorptive semiring and for computing the temporal reachability of nodes. We also describe the procedure for computing temporal weak and strong connectivity components using the appropriate closure. This approach can also be used for the analysis of groups that are determined by other equivalence relations on the given network. The described procedures are available as a Python library TQ. We tested the algorithms on real networks, the Franzosi's violence network and the Reuters terror news network.
|
