Matching Items (2)
Description
This dissertation studies routing in small-world networks such as grids plus long-range edges and real networks. Kleinberg showed that geography-based greedy routing in a grid-based network takes an expected number of steps polylogarithmic in the network size, thus justifying empirical efficiency observed beginning with Milgram. A counterpart for the grid-based model is provided; it creates all edges deterministically and shows an asymptotically matching upper bound on the route length. The main goal is to improve greedy routing through a decentralized machine learning process. Two considered methods are based on weighted majority and an algorithm of de Farias and Megiddo, both learning from feedback using ensembles of experts. Tests are run on both artificial and real networks, with decentralized spectral graph embedding supplying geometric information for real networks where it is not intrinsically available. An important measure analyzed in this work is overpayment, the difference between the cost of the method and that of the shortest path. Adaptive routing overtakes greedy after about a hundred or fewer searches per node, consistently across different network sizes and types. Learning stabilizes, typically at overpayment of a third to a half of that by greedy. The problem is made more difficult by eliminating the knowledge of neighbors' locations or by introducing uncooperative nodes. Even under these conditions, the learned routes are usually better than the greedy routes. The second part of the dissertation is related to the community structure of unannotated networks. A modularity-based algorithm of Newman is extended to work with overlapping communities (including considerably overlapping communities), where each node locally makes decisions to which potential communities it belongs. To measure quality of a cover of overlapping communities, a notion of a node contribution to modularity is introduced, and subsequently the notion of modularity is extended from partitions to covers. The final part considers a problem of network anonymization, mostly by the means of edge deletion. The point of interest is utility preservation. It is shown that a concentration on the preservation of routing abilities might damage the preservation of community structure, and vice versa.
ContributorsBakun, Oleg (Author) / Konjevod, Goran (Thesis advisor) / Richa, Andrea (Thesis advisor) / Syrotiuk, Violet R. (Committee member) / Czygrinow, Andrzej (Committee member) / Arizona State University (Publisher)
Created2011
Description
This dissertation is a study and translation of the Hereditary Household of the Han Celestial Master (Han tianshi shijia 漢天師世家), a hagiographical account of successive generations of the Zhang family patriarchs of Celestial Masters Daoism (Tianshi dao 天師道) at Dragon and Tiger Mountain (Longhu shan 龍虎山) in Jiangxi province that was compiled in stages between the late fourteenth and early seventeenth centuries. The Zhang family emerged in the late Tang or early Five dynasties period and rose to great prominence and power through the Song, Yuan, and Ming dynasties on the basis of the claim of direct and unbroken lineal descent from Zhang Daoling 張道陵 the ancestral Celestial Master whose covenant with the deified Laozi in 142 C.E. is a founding event of the Daoist religion. In this study I trace the lineal history of the Zhang family as presented in the Hereditary Household in chronological parallel to contrasting narratives found in official histories, epigraphy, and the literary record. This approach affords insight into the polemical nature of the text as an assertion of legitimacy and allows for a demonstration of how the work represents an attempt to create in writing an idealized past in order to win prestige in the present. It also affords the opportunity to scour the historical record in an attempt to ascertain a plausible timeframe for the origin of the movement and to explore the relationship of the Hereditary Household to earlier hagiographic works that may have informed it. This study also contextualizes the Hereditary Household in the post-Tang religious climate of China. In that period the establishment of lineal authenticity and institutional charisma through narratives of descent became a widespread tool of legitimation employed by Buddhists, Daoists, and Confucians in hopes of obtaining imperial recognition and patronage.
ContributorsAmato, Paul (Author) / Bokenkamp, Stephen R (Thesis advisor) / Chen, Huaiyu (Committee member) / Feldhaus, Anne (Committee member) / West, Stephen H. (Committee member) / Arizona State University (Publisher)
Created2016