本論文討論了幾個重要的用於網絡分析的圖結構以及相闋的算法設計問題，並著重討論了其中的組合結構及其在大規模網絡中之計算問題。根據這些結構在網絡所處之層次，我們將它們分成局部結構和全局結構來分別討論。 / 對於在大規模網絡中的緊密子圖探測問題和極大完全子圖枚舉問題，本論文提出了新概念和新算法。其一，對於一種名為k-truss的新型緊密子圖，提出了更快的內存算法和適用於在大規模網絡中尋找此種子圖的方法。其二，針對於傳統完全子圖枚舉算法的輸出過大的問題，提出了用於緊湊表示圖中一切極大完全子圖的新方法。采用此種方法，我們能夠在保證重要信息得到保留的情況下，顯著地減小輸出的體積同時提高計算速度。 / This thesis discusses a number of important structures for network analysis and their algorithmic results. Special attentions are paid to combinatorial structures and related computation problems in large networks. According to the granularity of the concepts, we shall distinguish between local and global objects and present them separately. / New algorithms and concepts are proposed for interesting arising problems in cohesive subgraph detection and maximal clique enumeration (MCE). Specifically, algorithms for k-truss, a new type of cohesive subgraphs, are proposed including a fast in-memory algorithm and techniques that handle large disk-resident networks. Motivated by the sheer size of output by classic MCE algorithms, a novel notion for a low-redundancy representation of the set of all maximal cliques is proposed, which enables effective use of maximal cliques and a faster computation of the reduced output. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Wang, Jia. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 58-62). / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Preliminaries --- p.2 / Chapter 3 --- Global Structures --- p.3 / Chapter 3.1 --- Component Decomposition --- p.4 / Chapter 3.2 --- Structures with Hierarchy --- p.6 / Chapter 3.2.1 --- k-cores --- p.6 / Chapter 3.2.2 --- k-trusses --- p.8 / Chapter 3.3 --- Improved Truss Computation [45] --- p.10 / Chapter 3.3.1 --- Notations --- p.11 / Chapter 3.3.2 --- Faster In-Memory Algorithm --- p.11 / Chapter 3.3.3 --- Handling Massive Graphs --- p.16 / Chapter 3.3.4 --- Bottom-Up Approach --- p.17 / Chapter 3.3.5 --- Top-k Trusses --- p.23 / Chapter 3.3.6 --- Empirical Study --- p.28 / Chapter 3.4 --- Summary --- p.33 / Chapter 4 --- Local Structures --- p.33 / Chapter 4.1 --- Small Cycles and Clustering Coefficients --- p.33 / Chapter 4.2 --- Maximal Cliques --- p.36 / Chapter 4.3 --- Redundancy-Aware MCE [46] --- p.36 / Chapter 4.3.1 --- Motivations --- p.38 / Chapter 4.3.2 --- τ-visible MCE --- p.41 / Chapter 4.3.3 --- Applications --- p.50 / Chapter 4.3.4 --- Empirical Study --- p.52 / Chapter 4.4 --- Summary --- p.56 / Chapter 5 --- Structures in Mid-Zone --- p.56 / Chapter 5.1 --- Densest Subgraph --- p.56 / Chapter 5.2 --- Relaxed Cliques --- p.57 / Chapter 6 --- Concluding Remarks --- p.58

University of Macau / Faculty of Science and Technology / Department of Electromechanical Engineering

In the operation of stochastic systems, and of queues in particular, it is important to recognize quickly the development in time of situations not compatible with their design criteria. Once such an anomalous condition is detected, it has to be decided, if the occurrence of that event can be attributed to chance or is due to a change in the parameters governing the system. This procedure of tracking the system is defined as monitoring. The design of a monitor and the selection of suitable threshold regions for monitoring a single server queue are the subjects of this thesis. The notion of profile curves, useful in formalizing monitoring schemes for queues, is also discussed. Finally, some numerical examples are presented to illustrate the performance of the monitor designed.

published_or_final_version / Civil and Structural Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Mechanical Engineering / Doctoral / Doctor of Philosophy

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Part I deals with the simulation of fluid dynamics using the lattice-Boltzmann method. Microfluidic devices often feature two-dimensional, repetitive arrays. Flows through such devices are pressure-driven and confined by solid walls. We have defined new adaptive generalised periodic boundary conditions to represent the effects of outer solid walls, and are thus able to exploit the periodicity of the array by simulating the flow through one unit cell in lieu of the entire device. The so-calculated fully developed flow describes the flow through the entire array accurately, but with computational requirements that are reduced according to the dimensions of the array. / Part II discusses the problem of separating macromolecules like proteins or DNA coils. The reliable separation of such molecules is a crucial task in molecular biology. The use of Brownian ratchets as mechanisms for the separation of such particles has been proposed and discussed during the last decade. Pressure-driven flows have so far been dismissed as possible driving forces for Brownian ratchets, as they do not generate ratchet asymmetry. We propose a microfluidic design that uses pressure-driven flows to create asymmetry and hence allows particle separation. The dependence of the asymmetry on various factors of the microfluidic geometry is discussed. We further exemplify the feasibility of our approach using Brownian dynamics simulations of particles of different sizes in such a device. The results show that ratchet-based particle separation using flows as the driving force is possible. Simulation results and ratchet theory predictions are in excellent agreement. / Part III deals with the co-evolution of networks and dynamic models. A group of agents occupies the nodes of a network, which defines the relationship between these agents. The evolution of the agents is defined by the rules of the dynamic model and depends on the relationship between agents, i.e., the state of the network. In return, the evolution of the network depends on the state of the dynamic model. The concept is introduced through the adaptive SIS model. We show that the previously used criterion determining the critical infected fraction, i.e., the number of infected agents required to sustain the epidemic, is inappropriate for this model. We introduce a different criterion and show that the critical infected fraction so determined is in good agreement with results obtained by numerical simulations. / This thesis comprises three parts, reporting research results in Fluid Dynamics (Part I), Particle Separation (Part II) and Co-evolving Networks (Part III). / We further discuss the concept of co-evolving dynamics using the Snowdrift Game as a model paradigm. Co-evolution occurs through agents cutting dissatisfied links and rewiring to other agents at random. The effect of co-evolution on the emergence of cooperation is discussed using a mean-field theory and numerical simulations. A transition between a connected and a disconnected, highly cooperative state of the system is observed, and explained using the mean-field model. Quantitative deviations regarding the level of cooperation in the disconnected regime can be fully resolved through an improved mean-field theory that includes the effect of random fluctuations into its model. / Graeser, Oliver = 自主個體為本系統與在流體力學、分子分離、共同演化網絡上的應用 / 顧皓森. / Adviser: Hui Pak-Ming. / Source: Dissertation Abstracts International, Volume: 73-01, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 204-216). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Graeser, Oliver = Zi zhu ge ti wei ben xi tong yu zai liu ti li xue, fen zi fen li, gong tong yan hua wang luo shang de ying yong / Gu Haosen.

This thesis describes a new approach to achieving high quality distributed garbage collection using the Train Algorithm. This algorithm has been investigated for its ability to provide high quality collection in a variety of contexts, including persistent object systems and distributed object systems. Prior literature on the distributed Train Algorithm suggests that safe, complete, asynchronous, and scalable collection can be attained, however an approach that achieves this combination of behaviour has yet to emerge. The mechanisms and policies described in this thesis are unique in their ability to exploit the distributed Train Algorithm in a manner that displays all four desirable qualities. Further the mechanisms allow any number of mutator and collector threads to operate concurrently within a site; this is also a unique property amongst train-based mechanisms (distributed or otherwise). Confidence in the quality of the approach promoted in this thesis is obtained via a top-down approach. Firstly a concise behavioural model is introduced to capture fundamental requirements for safe and complete behaviour from train-based collection mechanisms. The model abstracts over the techniques previously introduced under the banner of the Train Algorithm. It serves as a self- contained template for correct train-based collection that is independent of a target object system for deployment of the algorithm. Secondly a means to instantiate the model in a distributed object system is described. The instantiation includes well-established techniques from prior literature, and via the model these are correctly refined and reorganised with new techniques to achieve asynchrony, scalability, and support for concurrency. The result is a flexible approach that allows a distributed system to exhibit a variety of local collection mechanisms and policies, while ensuring their interaction is safe, complete, asynchronous, and scalable regardless of the local choices made by each site. Additional confidence in the properties of the new approach is obtained from implementation within a distributed object system simulation. The implementation provides some insight into the practical issues that arise through the combination of distribution, concurrent execution within sites, and train-based collection. Executions of the simulation system are used to verify that safe collection is observed at all times, and obtain evidence that asynchrony, scalability, and concurrency can be observed in practice. / Thesis (Ph.D.)--School of Computer Science, 2004.

This thesis describes a new approach to achieving high quality distributed garbage collection using the Train Algorithm. This algorithm has been investigated for its ability to provide high quality collection in a variety of contexts, including persistent object systems and distributed object systems. Prior literature on the distributed Train Algorithm suggests that safe, complete, asynchronous, and scalable collection can be attained, however an approach that achieves this combination of behaviour has yet to emerge. The mechanisms and policies described in this thesis are unique in their ability to exploit the distributed Train Algorithm in a manner that displays all four desirable qualities. Further the mechanisms allow any number of mutator and collector threads to operate concurrently within a site; this is also a unique property amongst train-based mechanisms (distributed or otherwise). Confidence in the quality of the approach promoted in this thesis is obtained via a top-down approach. Firstly a concise behavioural model is introduced to capture fundamental requirements for safe and complete behaviour from train-based collection mechanisms. The model abstracts over the techniques previously introduced under the banner of the Train Algorithm. It serves as a self- contained template for correct train-based collection that is independent of a target object system for deployment of the algorithm. Secondly a means to instantiate the model in a distributed object system is described. The instantiation includes well-established techniques from prior literature, and via the model these are correctly refined and reorganised with new techniques to achieve asynchrony, scalability, and support for concurrency. The result is a flexible approach that allows a distributed system to exhibit a variety of local collection mechanisms and policies, while ensuring their interaction is safe, complete, asynchronous, and scalable regardless of the local choices made by each site. Additional confidence in the properties of the new approach is obtained from implementation within a distributed object system simulation. The implementation provides some insight into the practical issues that arise through the combination of distribution, concurrent execution within sites, and train-based collection. Executions of the simulation system are used to verify that safe collection is observed at all times, and obtain evidence that asynchrony, scalability, and concurrency can be observed in practice. / Thesis (Ph.D.)--School of Computer Science, 2004.