Current Search: Deo, Narsingh (x)
View All Items
 Title
 ALGORITHMS FOR DISCOVERING COMMUNITIES IN COMPLEX NETWORKS.
 Creator

Balakrishnan, Hemant, Deo, Narsingh, University of Central Florida
 Abstract / Description

It has been observed that realworld random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closelyknit groups that are locally dense and globally sparse. These closelyknit groups are termed communities. Nodes within a community are similar in some aspect. For example in a WWW network, communities might consist of web pages that share similar contents. Mining these communities facilitates better understanding of their evolution and...
Show moreIt has been observed that realworld random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closelyknit groups that are locally dense and globally sparse. These closelyknit groups are termed communities. Nodes within a community are similar in some aspect. For example in a WWW network, communities might consist of web pages that share similar contents. Mining these communities facilitates better understanding of their evolution and topology, and is of great theoretical and commercial significance. Community related research has focused on two main problems: community discovery and community identification. Community discovery is the problem of extracting all the communities in a given network, whereas community identification is the problem of identifying the community, to which, a given set of nodes belong. We make a comparative study of various existing communitydiscovery algorithms. We then propose a new algorithm based on bibliographic metrics, which addresses the drawbacks in existing approaches. Bibliographic metrics are used to study similarities between publications in a citation network. Our algorithm classifies nodes in the network based on the similarity of their neighborhoods. One of the drawbacks of the current communitydiscovery algorithms is their computational complexity. These algorithms do not scale up to the enormous size of the realworld networks. We propose a hashtablebased technique that helps us compute the bibliometric similarity between nodes in O(m ?) time. Here m is the number of edges in the graph and ?, the largest degree. Next, we investigate different centrality metrics. Centrality metrics are used to portray the importance of a node in the network. We propose an algorithm that utilizes centrality metrics of the nodes to compute the importance of the edges in the network. Removal of the edges in ascending order of their importance breaks the network into components, each of which represent a community. We compare the performance of the algorithm on synthetic networks with a known community structure using several centrality metrics. Performance was measured as the percentage of nodes that were correctly classified. As an illustration, we model the ucf.edu domain as a web graph and analyze the changes in its properties like densification power law, edge density, degree distribution, diameter, etc., over a fiveyear period. Our results show superlinear growth in the number of edges with time. We observe (and explain) that despite the increase in average degree of the nodes, the edge density decreases with time.
Show less  Date Issued
 2006
 Identifier
 CFE0001473, ucf:47085
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0001473
 Title
 GRAPH THEORETIC MODELING: CASE STUDIES IN REDUNDANT ARRAYS OF INDEPENDENT DISKS AND NETWORK DEFENSE.
 Creator

Nanda, Sanjeeb, Deo, Narsingh, University of Central Florida
 Abstract / Description

Graph theoretic modeling has served as an invaluable tool for solving a variety of problems since its introduction in Euler's paper on the Bridges of Königsberg in 1736 . Two amongst them of contemporary interest are the modeling of Redundant Arrays of Inexpensive Disks (RAID), and the identification of network attacks. While the former is vital to the protection and uninterrupted availability of data, the latter is crucial to the integrity of systems comprising networks. Both are of...
Show moreGraph theoretic modeling has served as an invaluable tool for solving a variety of problems since its introduction in Euler's paper on the Bridges of Königsberg in 1736 . Two amongst them of contemporary interest are the modeling of Redundant Arrays of Inexpensive Disks (RAID), and the identification of network attacks. While the former is vital to the protection and uninterrupted availability of data, the latter is crucial to the integrity of systems comprising networks. Both are of practical importance due to the continuing growth of data and its demand at increasing numbers of geographically distributed locations through the use of networks such as the Internet. The popularity of RAID has soared because of the enhanced I/O bandwidths and large capacities they offer at low cost. However, the demand for bigger capacities has led to the use of larger arrays with increased probability of random disk failures. This has motivated the need for RAID systems to tolerate two or more disk failures, without sacrificing performance or storage space. To this end, we shall first perform a comparative study of the existing techniques that achieve this objective. Next, we shall devise novel graphtheoretic algorithms for placing data and parity in arrays of n disks (n ≥ 3) that can recover from two random disk failures, for n = p – 1, n = p and n = 2p – 2, where p is a prime number. Each shall be shown to utilize an optimal ratio of space for storing parity. We shall also show how to extend the algorithms to arrays with an arbitrary number of disks, albeit with nonoptimal values for the aforementioned ratio. The growth of the Internet has led to the increased proliferation of malignant applications seeking to breach the security of networked systems. Hence, considerable effort has been focused on detecting and predicting the attacks they perpetrate. However, the enormity of the Internet poses a challenge to representing and analyzing them by using scalable models. Furthermore, forecasting the systems that they are likely to exploit in the future is difficult due to the unavailability of complete information on network vulnerabilities. We shall present a technique that identifies attacks on large networks using a scalable model, while filtering for false positives and negatives. Furthermore, it also forecasts the propagation of security failures proliferated by attacks over time and their likely targets in the future.
Show less  Date Issued
 2007
 Identifier
 CFE0001919, ucf:47475
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0001919
 Title
 GRAPHTHEORETIC APPROACH TO MODELING PROPAGATION AND CONTROL OF NETWORK WORMS.
 Creator

Nikoloski, Zoran, Deo, Narsingh, University of Central Florida
 Abstract / Description

In today's networkdependent society, cyber attacks with network worms have become the predominant threat to confidentiality, integrity, and availability of network computing resources. Despite ongoing research efforts, there is still no comprehensive networksecurity solution aimed at controling largescale worm propagation. The aim of this work is fivefold: (1) Developing an accurate combinatorial model of worm propagation that can facilitate the analysis of worm control strategies, (2)...
Show moreIn today's networkdependent society, cyber attacks with network worms have become the predominant threat to confidentiality, integrity, and availability of network computing resources. Despite ongoing research efforts, there is still no comprehensive networksecurity solution aimed at controling largescale worm propagation. The aim of this work is fivefold: (1) Developing an accurate combinatorial model of worm propagation that can facilitate the analysis of worm control strategies, (2) Building an accurate epidemiological model for the propagation of a worm employing local strategies, (3) Devising distributed architecture and algorithms for detection of worm scanning activities, (4) Designing effective control strategies against the worm, and (5) Simulation of the developed models and strategies on large, scalefree graphs representing realworld communication networks. The proposed pairapproximation model uses the information about the network structureorder, size, degree distribution, and transitivity. The empirical study of propagation on large scalefree graphs is in agreement with the theoretical analysis of the proposed pairapproximation model. We, then, describe a natural generalization of the classical copsandrobbers gamea combinatorial model of worm propagation and control. With the help of this game on graphs, we show that the problem of containing the worm is NPhard. Six novel nearoptimal control strategies are devised: combination of static and dynamic immunization, reactive dynamic and invariant dynamic immunization, soft quarantining, predictive trafficblocking, and contacttracing. The analysis of the predictive dynamic trafficblocking, employing only local information, shows that the worm can be contained so that 40\% of the network nodes are not affected. Finally, we develop the Detection via Distributed Blackholes architecture and algorithm which reflect the propagation strategy used by the worm and the salient properties of the network. Our distributed detection algorithm can detect the worm scanning activity when only 1.5% of the network has been affected by the propagation. The proposed models and algorithms are analyzed with an individualbased simulation of worm propagation on realistic scalefree topologies.
Show less  Date Issued
 2005
 Identifier
 CFE0000640, ucf:46521
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0000640
 Title
 ANALYZING THE COMMUNITY STRUCTURE OF WEBLIKE NETWORKS: MODELS AND ALGORITHMS.
 Creator

Cami, Aurel, Deo, Narsingh, University of Central Florida
 Abstract / Description

This dissertation investigates the community structure of weblike networks (i.e., large, random, reallife networks such as the World Wide Web and the Internet). Recently, it has been shown that many such networks have a locally dense and globally sparse structure with certain small, dense subgraphs occurring much more frequently than they do in the classical ErdösRényi random graphs. This peculiaritywhich is commonly referred to as community structurehas been observed in...
Show moreThis dissertation investigates the community structure of weblike networks (i.e., large, random, reallife networks such as the World Wide Web and the Internet). Recently, it has been shown that many such networks have a locally dense and globally sparse structure with certain small, dense subgraphs occurring much more frequently than they do in the classical ErdösRényi random graphs. This peculiaritywhich is commonly referred to as community structurehas been observed in seemingly unrelated networks such as the Web, email networks, citation networks, biological networks, etc. The pervasiveness of this phenomenon has led many researchers to believe that such cohesive groups of nodes might represent meaningful entities. For example, in the Web such tightlyknit groups of nodes might represent pages with a common topic, geographical location, etc., while in the neural networks they might represent evolved computational units. The notion of community has emerged in an effort to formalize the empirical observation of the locally dense globally sparse structure of weblike networks. In the broadest sense, a community in a weblike network is defined as a group of nodes that induces a dense subgraph which is sparsely linked with the rest of the network. Due to a wide array of envisioned applications, ranging from crawlers and search engines to network security and network compression, there has recently been a widespread interest in finding efficient communitymining algorithms. In this dissertation, the community structure of weblike networks is investigated by a combination of analytical and computational techniques: First, we consider the problem of modeling the weblike networks. In the recent years, many new random graph models have been proposed to account for some recently discovered properties of weblike networks that distinguish them from the classical random graphs. The vast majority of these random graph models take into account only the addition of new nodes and edges. Yet, several empirical observations indicate that deletion of nodes and edges occurs frequently in weblike networks. Inspired by such observations, we propose and analyze two dynamic random graph models that combine node and edge addition with a uniform and a preferential deletion of nodes, respectively. In both cases, we find that the random graphs generated by such models follow powerlaw degree distributions (in agreement with the degree distribution of many weblike networks). Second, we analyze the expected density of certain small subgraphssuch as defensive alliances on three and four nodesin various random graphs models. Our findings show that while in the binomial random graph the expected density of such subgraphs is very close to zero, in some dynamic random graph models it is much larger. These findings converge with our results obtained by computing the number of communities in some Web crawls. Next, we investigate the computational complexity of the communitymining problem under various definitions of community. Assuming the definition of community as a global defensive alliance, or a global offensive alliance we proveusing transformations from the dominating set problemthat finding optimal communities is an NPcomplete problem. These and other similar complexity results coupled with the fact that many weblike networks are huge, indicate that it is unlikely that fast, exact sequential algorithms for mining communities may be found. To handle this difficulty we adopt an algorithmic definition of community and a simpler version of the communitymining problem, namely: find the largest community to which a given set of seed nodes belong. We propose several greedy algorithms for this problem: The first proposed algorithm starts out with a set of seed nodesthe initial communityand then repeatedly selects some nodes from community's neighborhood and pulls them in the community. In each step, the algorithm uses clustering coefficienta parameter that measures the fraction of the neighbors of a node that are neighbors themselvesto decide which nodes from the neighborhood should be pulled in the community. This algorithm has time complexity of order , where denotes the number of nodes visited by the algorithm and is the maximum degree encountered. Thus, assuming a powerlaw degree distribution this algorithm is expected to run in nearlinear time. The proposed algorithm achieved good accuracy when tested on some real and computergenerated networks: The fraction of community nodes classified correctly is generally above 80% and often above 90% . A second algorithm based on a generalized clustering coefficient, where not only the first neighborhood is taken into account but also the second, the third, etc., is also proposed. This algorithm achieves a better accuracy than the first one but also runs slower. Finally, a randomized version of the second algorithm which improves the time complexity without affecting the accuracy significantly, is proposed. The main target application of the proposed algorithms is focused crawlingthe selective search for web pages that are relevant to a predefined topic.
Show less  Date Issued
 2005
 Identifier
 CFE0000900, ucf:46726
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0000900
 Title
 ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS.
 Creator

Tener, Greg, Deo, Narsingh, University of Central Florida
 Abstract / Description

The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualizationrefinement paradigm, pioneered by Brendan McKay in 1981 with his...
Show moreThe graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualizationrefinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representativean approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nautylike algorithms. This dissertation investigates why these graph families pose difficulty for individualizationrefinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualizationrefinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial timethus obviating the only known exponential upperbound on individualizationrefinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guidetree data structure of the preceding technique to use a stronger vertexinvariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.
Show less  Date Issued
 2009
 Identifier
 CFE0002894, ucf:48018
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0002894
 Title
 Computing a diameterconstrained minimum spanning tree.
 Creator

Abdalla, Ayman Mahmoud, Deo, Narsingh, Engineering and Computer Science
 Abstract / Description

University of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NPcomplete for all values of k; 4
Show moreUniversity of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NPcomplete for all values of k; 4 <= k <= (n  2), except when all edgeweights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a datastructure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space.
Show less  Date Issued
 2001
 Identifier
 CFR0002215, ucf:52914
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFR0002215
 Title
 Scalable Network Design and Management with Decentralized Softwaredefined Networking.
 Creator

Atwal, Kuldip Singh, Bassiouni, Mostafa, Fu, Xinwen, Zou, Changchun, Deo, Narsingh, University of Central Florida
 Abstract / Description

Network softwarization is among the most significant innovations of computer networks in the last few decades. The lack of uniform and programmable interfaces for network management led to the design of OpenFlow protocol for the university campuses and enterprise networks. This breakthrough coupled with other similar efforts led to an emergence of two complementary but independent paradigms called softwaredefined networking (SDN) and network function virtualization (NFV). As of this writing,...
Show moreNetwork softwarization is among the most significant innovations of computer networks in the last few decades. The lack of uniform and programmable interfaces for network management led to the design of OpenFlow protocol for the university campuses and enterprise networks. This breakthrough coupled with other similar efforts led to an emergence of two complementary but independent paradigms called softwaredefined networking (SDN) and network function virtualization (NFV). As of this writing, these paradigms are becoming the defacto norms of wired and wireless networks alike. This dissertation mainly addresses the scalability aspect of SDN for multiple network types. Although centralized control and separation of control and data planes play a pivotal role for ease of network management, these concepts bring in many challenges as well. Scalability is among the most crucial challenges due to the unprecedented growth of computer networks in the past few years. Therefore, we strive to grapple with this problem in diverse networking scenarios and propose novel solutions by harnessing capabilities provided by SDN and other related technologies. Specifically, we present the techniques to deploy SDN at the Internet scale and to extend the concepts of softwarization for mobile access networks and vehicular networks. Multiple optimizations are employed to mitigate latency and other overheads that contribute to achieve performance gains. Additionally, by taking care of sparse connectivity and high mobility, the intrinsic constraints of centralization for wireless adhoc networks are addressed in a systematic manner. The stateoftheart virtualization techniques are coupled with cloud computing methods to exploit the potential of softwarization in general and SDN in particular. Finally, by tapping into the capabilities of machine learning techniques, an SDNbased solution is proposed that inches closer towards the longstanding goal of selfdriving networks. Extensive experiments performed on a largescale testbed corroborates effectiveness of our approaches.
Show less  Date Issued
 2019
 Identifier
 CFE0007600, ucf:52543
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007600
 Title
 A Compilerbased Framework for Automatic Extraction of Program Skeletons for Exascale Hardware/Software Codesign.
 Creator

Rudraiah Dakshinamurthy, Amruth, Dechev, Damian, Heinrich, Mark, Deo, Narsingh, University of Central Florida
 Abstract / Description

The design of highperformance computing architectures requires performance analysis of largescale parallel applications to derive various parameters concerning hardware design and software development. The process of performance analysis and benchmarking an application can be done in several ways with varying degrees of fidelity. One of the most costeffective ways is to do a coarsegrained study of largescale parallel applications through the use of program skeletons. The concept of a `...
Show moreThe design of highperformance computing architectures requires performance analysis of largescale parallel applications to derive various parameters concerning hardware design and software development. The process of performance analysis and benchmarking an application can be done in several ways with varying degrees of fidelity. One of the most costeffective ways is to do a coarsegrained study of largescale parallel applications through the use of program skeletons. The concept of a ``program skeleton'' that we discuss in this paper is an abstracted program that is derived from a larger program where source code that is determined to be irrelevant is removed for the purposes of the skeleton. In this work, we develop a semiautomatic approach for extracting program skeletons based on compiler program analysis. We demonstrate correctness of our skeleton extraction process by comparing details from communication traces, as well as show the performance speedup of using skeletons by running simulations in the SST/macro simulator. Extracting such a program skeleton from a largescale parallel program requires a substantial amount of manual effort and often introduces human errors. We outline a semiautomatic approach for extracting program skeletons from largescale parallel applications that reduces cost and eliminates errors inherent in manual approaches. Our skeleton generation approach is based on the use of the extensible and opensource ROSE compiler infrastructure that allows us to perform flow and dependency analysis on larger programs in order to determine what code can be removed from the program to generate a skeleton.
Show less  Date Issued
 2013
 Identifier
 CFE0004743, ucf:49795
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0004743
 Title
 Algorithms for Community Identification in Complex Networks.
 Creator

Vasudevan, Mahadevan, Deo, Narsingh, Hughes, Charles, Guha, Ratan, Chatterjee, Mainak, Zhao, Yue, University of Central Florida
 Abstract / Description

Complex networks such as the Internet, the World Wide Web (WWW), and various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the Erd(&)#246;sR(&)#233;nyi random graphs. In particular, properties such as degree distribution, network distance, transitivity and clustering coefficient of these networks have been empirically shown to diverge from classical random networks. Existence of communities is one such...
Show moreComplex networks such as the Internet, the World Wide Web (WWW), and various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the Erd(&)#246;sR(&)#233;nyi random graphs. In particular, properties such as degree distribution, network distance, transitivity and clustering coefficient of these networks have been empirically shown to diverge from classical random networks. Existence of communities is one such property inherent to these networks. A community may informally be defined as a locallydense induced subgraph, of significant size, in a large globallysparse graph. Recent empirical results reveal communities in networks spanning across different disciplines () physics, statistics, sociology, biology, and linguistics. At least two different questions may be posed on the community structure in large networks: (i) Given a network, detect or extract all (i.e., sets of nodes that constitute) communities; and (ii) Given a node in the network, identify the best community that the given node belongs to, if there exists one. Several algorithms have been proposed to solve the former problem, known as Community Discovery. The latter problem, known as Community Identification, has also been studied, but to a much smaller extent. Both these problems have been shown to be NPcomplete, and a number of approximate algorithms have been proposed in recent years. A comprehensive taxonomy of the existing community detection algorithms is presented in this work. Global exploration of these complex networks to pull out communities (community discovery) is time and memory consuming. A more confined approach to mine communities in a given network is investigated in this research. Identifying communities does not require the knowledge of the entire graph. Community identification algorithms exist in the literature, but to a smaller extent. The dissertation presents a thorough description and analysis of the existing techniques to identify communities in large networks. Also a novel heuristic for identifying the community to which a given seed node belongs using only its neighborhood information is presented. An improved definition of a community based on the average degree of the induced subgraph is discussed thoroughly and it is compared with the various definitions in the literature. Next, a faster and accurate algorithm to identify communities in complex networks based on maximizing the average degree is described. The divisive nature of the algorithm (as against the existing agglomerative methods) efficiently identifies communities in large complex networks. The performance of the algorithm on several synthetic and realworld complex networks has also been thoroughly investigated.
Show less  Date Issued
 2012
 Identifier
 CFE0004294, ucf:49463
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0004294
 Title
 Network Partitioning in Distributed AgentBased Models.
 Creator

Petkova, Antoniya, Deo, Narsingh, Hughes, Charles, Bassiouni, Mostafa, Shaykhian, Gholam, University of Central Florida
 Abstract / Description

AgentBased Models (ABMs) are an emerging simulation paradigm for modeling complex systems, comprised of autonomous, possibly heterogeneous, interacting agents. The utility of ABMs lies in their ability to represent such complex systems as selforganizing networks of agents. Modeling and understanding the behavior of complex systems usually occurs at large and representative scales, and often obtaining and visualizing of simulation results in realtime is critical.The realtime requirement...
Show moreAgentBased Models (ABMs) are an emerging simulation paradigm for modeling complex systems, comprised of autonomous, possibly heterogeneous, interacting agents. The utility of ABMs lies in their ability to represent such complex systems as selforganizing networks of agents. Modeling and understanding the behavior of complex systems usually occurs at large and representative scales, and often obtaining and visualizing of simulation results in realtime is critical.The realtime requirement necessitates the use of inmemory computing, as it is dif?cult and challenging to handle the latency and unpredictability of disk accesses. Combining this observation with the scale requirement emphasizes the need to use parallel and distributed computing platforms, such as MPIenabled CPU clusters. Consequently, the agent population must be "partitioned" across different CPUs in a cluster. Further, the typically high volume of interactions among agents can quickly become a signi?cant bottleneck for realtime or largescale simulations. The problem is exacerbated if the underlying ABM network is dynamic and the interprocess communication evolves over the course of the simulation. Therefore, it is critical to develop topologyaware partitioning mechanisms to support such large simulations.In this dissertation, we demonstrate that distributed agentbased model simulations bene?t from the use of graph partitioning algorithms that involve a local, neighborhoodbased perspective. Such methods do not rely on global accesses to the network and thus are more scalable. In addition, we propose two partitioning schemes that consider the bottomup individualcentric nature of agentbased modeling. The ?rst technique utilizes labelpropagation community detection to partition the dynamic agent network of an ABM. We propose a latencyhiding, seamless integration of community detection in the dynamics of a distributed ABM. To achieve this integration, we exploit the similarity in the process flow patterns of a labelpropagation communitydetection algorithm and selforganizing ABMs.In the second partitioning scheme, we apply a combination of the Guided Local Search (GLS) and Fast Local Search (FLS) metaheuristics in the context of graph partitioning. The main driving principle of GLS is the dynamic modi?cation of the objective function to escape local optima. The algorithm augments the objective of a local search, thereby transforming the landscape structure and escaping a local optimum. FLS is a local search heuristic algorithm that is aimed at reducing the search space of the main search algorithm. It breaks down the space into subneighborhoods such that inactive subneighborhoods are removed from the search process. The combination of GLS and FLS allowed us to design a graph partitioning algorithm that is both scalable and sensitive to the inherent modularity of realworld networks.
Show less  Date Issued
 2017
 Identifier
 CFE0006903, ucf:51706
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006903