Geodesic-based Properties in Complex Networks

In the modern age of the Internet, complex large-scale networks are most likely a part of our daily interactions. From social networks like Facebook and Twitter, to technological systems such as World Wide Web and the Internet, to cell structure and traffic routes, a wide variety of systems can be described by complex networks, making their impact and relevance indisputable. To understand the behavior and performance of complicated systems as a whole, we need to expand our understanding of the topology and structure of underlying network, which makes the investigation of network measures that reflect the most salient properties of complex large-scale networks a high demand area in the network science community. This thesis, investigates multiple geodesic-based properties in complex networks, which provide beneficial insight to network behavior and performance. We adapt a combinatorial measure of negative curvature (also called hyperbolicity) to parameterized finite networks and show that a variety of biological and social networks are hyperbolic. We also look into the complexity of a geodesic-based property known as strong metric dimension and show the approximation and inapproximability results for the problem of calculating the strong metric dimension of a graph with n nodes. Finally, we investigate a geodesic-based property that indicates the privacy violation in large–networks under active attacks. Our result provides some insight regarding prevention of privacy violation and designing topology of networks, as well as shedding light on privacy violation properties of real social networks and a large number of synthetic networks.