A. James Clark School of Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/1654

The collections in this community comprise faculty research works, as well as graduate theses and dissertations.

Browse

Subject: search.filters.subject.Random graphs

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    ADVENTURES ON NETWORKS: DEGREES AND GAMES
    (2015) Pal, Siddharth; Makowski, Armand; La, Richard; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    A network consists of a set of nodes and edges with the edges representing pairwise connections between nodes. Examples of real-world networks include the Internet, the World Wide Web, social networks and transportation networks often modeled as random graphs. In the first half of this thesis, we explore the degree distributions of such random graphs. In homogeneous networks or graphs, the behavior of the (generic) degree of a single node is often thought to reflect the degree distribution of the graph defined as the usual fractions of nodes with given degree. To study this preconceived notion, we introduce a general framework to discuss the conditions under which these two degree distributions coincide asymptotically in large random networks. Although Erdos-Renyi graphs along with other well known random graph models satisfy the aforementioned conditions, we show that there might be homogeneous random graphs for which such a conclusion may fail to hold. A counterexample to this common notion is found in the class of random threshold graphs. An implication of this finding is that random threshold graphs cannot be used as a substitute to the Barabasi-Albert model for scale-free network modeling, as proposed in some works. Since the Barabasi-Albert model was proposed, other network growth models were introduced that were shown to generate scale-free networks. We study one such basic network growth model, called the fitness model, which captures the inherent attributes of individual nodes through fitness values (drawn from a fitness distribution) that influence network growth. We characterize the tail of the network-wide degree distribution through the fitness distribution and demonstrate that the fitness model is indeed richer than the Barabasi-Albert model, in that it is capable of producing power-law degree distributions with varying parameters along with other non-Poisson degree distributions. In the second half of the thesis, we look at the interactions between nodes in a game-theoretic setting. As an example, these nodes could represent interacting agents making decisions over time while the edges represent the dependence of their payoffs on the decisions taken by other nodes. We study learning rules that could be adopted by the agents so that the entire system of agents reaches a desired operating point in various scenarios motivated by practical concerns facing engineering systems. For our analysis, we abstract out the network and represent the problem in the strategic-form repeated game setting. We consider two classes of learning rules -- a class of better-reply rules and a new class of rules, which we call, the class of monitoring rules. Motivated by practical concerns, we first consider a scenario in which agents revise their actions asynchronously based on delayed payoff information. We prove that, under the better-reply rules (when certain mild assumptions hold), the action profiles played by the agents converge almost surely to a pure-strategy Nash equilibrium (PSNE) with finite expected convergence time in a large class of games called generalized weakly acyclic games (GWAGs). A similar result is shown to hold for the monitoring rules in GWAGs and also in games satisfying a payoff interdependency structure. Secondly, we investigate a scenario in which the payoff information is unreliable, causing agents to make erroneous decisions occasionally. When the agents follow the better-reply rules and the payoff information becomes more accurate over time, we demonstrate the agents will play a PSNE with probability tending to one in GWAGs. Under a similar setting, when the agents follow the monitoring rule, we show that the action profile weakly converges to certain characterizable PSNE(s). Finally, we study a scenario where an agent might erroneously execute an intended action from time to time. Under such a setting, we show that the monitoring rules ensure that the system reaches PSNE(s) which are resilient to deviations by potentially multiple agents.
  • Thumbnail Image
    Item
    RANDOM GRAPH MODELING OF KEY DISTRIBUTION SCHEMES IN WIRELESS SENSOR NETWORKS
    (2011) Yagan, Osman; Makowski, Armand M; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Wireless sensor networks (WSNs) are distributed collections of sensors with limited capabilities for computations and wireless communications. It is envisioned that such networks will be deployed in hostile environments where communications are monitored, and nodes are subject to capture and surreptitious use by an adversary. Thus, cryptographic protection will be needed to ensure secure communications, as well as to support sensor-capture detection, key revocation and sensor disabling. Recently, random key predistribution schemes have been introduced to address these issues, and they are by now a widely accepted solution for establishing security in WSNs. The main goal of the dissertation is to investigate and compare two popular random key predistribution schemes, namely the Eschenauer-Gligor (EG) scheme and the pairwise key distribution scheme of Chan, Perrig and Song. We investigate both schemes through their induced random graph models and develop scaling laws that corresponds to desirable network properties, e.g., absence of secure nodes that are isolated, secure connectivity, resiliency against attacks, scalability, and low memory load - We obtain conditions on the scheme parameters so that these properties occur with high probability as the number of nodes becomes large. We then compare these two schemes explaining their relative advantages and disadvantages, as well as their feasibility for several WSN applications. In the process, we first focus on the "full visibility" case, where sensors are all within communication range of each other. This assumption naturally leads to studying the random graph models induced by the aforementioned key distribution schemes, namely the random key graph and the random pairwise graph, respectively. In a second step, we remove the assumption of full visibility by integrating a wireless communication model with the random graph models induced under full visibility. We study the connectivity of WSNs under this new model and obtain conditions (for both schemes) that lead to the secure connectivity of the
  • Thumbnail Image
    Item
    Random Codes and Graphs for Secure Communication
    (2009) Anthapadmanabhan, Nagaraj Prasanth; Barg, Alexander; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation considers two groups of problems related to secure communication. The first line of research is devoted to theoretical problems of copyright protection of digital content. Embedding identification data in the content is a well-developed technique of content protection known under the name of fingerprinting. Schemes that provide such protection are known as fingerprinting codes in the literature. We study limits of the number of users of a fingerprinting system as well as constructions of low-complexity fingerprinting codes that support a large number of users. The second problem that is addressed in the dissertation relates to connectivity analysis of ad hoc wireless networks. One of the basic requirements in such environments is to ensure that none of the nodes are completely isolated from the network. We address the problem of characterizing threshold parameters for node isolation that enable the system designer to choose the power needed for network operation based on the outage probability of links in the network. The methods of this research draw from coding theory, information theory and random graphs. An idea that permeates most results in this dissertation is the application of randomization both in the analysis of fingerprinting and node isolation. The main contributions of this dissertation belong in the area of fingerprinting and are described as follows. We derive new lower and upper bounds on the optimal trade-off between the number of users and the length of the fingerprints required to ensure reliability of the system, which we call fingerprinting capacity. Information-theoretic techniques employed in our proofs of bounds on capacity originate in coding theorems for channels with multiple inputs. Constructions of fingerprinting codes draw on methods of coding theory related to list decoding and code concatenation. We also analyze random graph models for ad hoc networks with link failures and secure sensor networks that employ randomized key distribution. We establish a precise zero-one law for node isolation in the model with link failures for nodes placed on the circle. We further generalize this result to obtain a one-law for secure sensor networks on some surfaces.