부산대학교 도서관

Network theory studies complex interdependencies, commonly observed in our interconnected world. Many of those networks express an important constraint leading to a characteristic order; examples include publication dates of papers in a citation network, dependency of packages in computer software, and prey species in a food web. If edges respect this order, they exist only if they are directed from one node to a node later in the order and there can be no cycles---we observe a Directed Acyclic Graph (DAG). So in a DAG a link between two nodes represents an order of the pair, not necessarily their similarity as links are often interpreted in standard network analysis. To better understand these common network topologies, we need to adapt our tools so that they respect the order implicit in a DAG. In this thesis our question is what are the implications of this order on the paths, observed in a network. In particular, we study the relation between network paths and geometric geodesics, the statistics of the longest path, the meaning of centrality, and community detection in DAGs. We demonstrate how the presence of an order of nodes changes the network structure itself, as well as the analysis of it.