{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/89028"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/89028","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Potential-based analysis of social, communication, and distributed networks","abstract":"In recent years, there has been a wide range of studies on the role of social and distributed networks in various disciplinary areas. In particular, availability of large amounts of data from online social networks and advances in control of distributed systems have drawn the attention of many researchers to exploit the connection between evolutionary behaviors in social, communication and distributed networks. In this thesis, we first revisit several well-known types of social and distributed networks and review some relevant results from the literature. Building on this, we present a set of new results related to four different types of problems, and identify several directions for future research. The study undertaken and the approaches adopted allow us to analyze the evolution of certain types of social and distributed networks and also to identify local and global patterns of their dynamics using some novel potential-theoretic techniques. Following the introduction and preliminaries, we focus on analyzing a specific type of distributed algorithm for quantized consensus known as an unbiased quantized algorithm where a set of agents interact locally in a network in order to reach a consensus. We provide tight expressions for the expected convergence time of such dynamics over general static and time-varying networks. Following this, we introduce new protocols using a special class of Markov chains known as Metropolis chains and obtain the fastest (as of today) randomized quantized consensus protocol. The bounds provided here considerably improve the state of the art over static and dynamic networks. We make a bridge between two classes of problems, namely distributed control problems and game problems. We analyze a class of distributed averaging dynamics known as Hegselmann-Krause opinion dynamics. Modeling such dynamics as a non-cooperative game problem, we elaborate on some of the evolutionary properties of such dynamics. In particular, we answer an open question related to the termination time of such dynamics by connecting the convergence time to the spectral gap of the adjacency matrices of underlying dynamics. This not only allows us to improve the best known upper bound, but also removes the dependency of termination time from the dimension of the ambient space. The approach adopted here can also be leveraged to connect the rate of increase of a so-called kinetic-s-energy associated with multi-agent systems to the spectral gap of their underlying dynamics. We describe a richer class of distributed systems where the agents involved in the network act in a more strategic manner. More specifically, we consider a class of resource allocation games over networks and study their evolution to some final outcomes such as Nash equilibria. We devise some simple distributed algorithms which drive the entire network to a Nash equilibrium in polynomial time for dense and hierarchical networks. In particular, we show that such games benefit from having low price of anarchy, and hence, can be used to model allocation systems which suffer from lack of coordination. This fact allows us to devise a distributed approximation algorithm within a constant gap of any pure-strategy Nash equilibrium over general networks. Subsequently we turn our attention to an important problem related to competition over social networks. We establish a hardness result for searching an equilibrium over a class of games known as competitive diffusion games, and provide some necessary conditions for existence of a pure-strategy Nash equilibrium in such games. In particular, we provide some concentration results related to the expected utility of the players over random graphs. Finally, we discuss some future directions by identifying several interesting problems and justify the importance of the underlying problems.","abstract_html":"In recent years, there has been a wide range of studies on the role of social and distributed networks in various disciplinary areas. In particular, availability of large amounts of data from online social networks and advances in control of distributed systems have drawn the attention of many researchers to exploit the connection between evolutionary behaviors in social, communication and distributed networks. In this thesis, we first revisit several well-known types of social and distributed networks and review some relevant results from the literature. Building on this, we present a set of new results related to four different types of problems, and identify several directions for future research. The study undertaken and the approaches adopted allow us to analyze the evolution of certain types of social and distributed networks and also to identify local and global patterns of their dynamics using some novel potential-theoretic techniques. Following the introduction and preliminaries, we focus on analyzing a specific type of distributed algorithm for quantized consensus known as an unbiased quantized algorithm where a set of agents interact locally in a network in order to reach a consensus. We provide tight expressions for the expected convergence time of such dynamics over general static and time-varying networks. Following this, we introduce new protocols using a special class of Markov chains known as Metropolis chains and obtain the fastest (as of today) randomized quantized consensus protocol. The bounds provided here considerably improve the state of the art over static and dynamic networks. We make a bridge between two classes of problems, namely distributed control problems and game problems. We analyze a class of distributed averaging dynamics known as Hegselmann-Krause opinion dynamics. Modeling such dynamics as a non-cooperative game problem, we elaborate on some of the evolutionary properties of such dynamics. In particular, we answer an open question related to the termination time of such dynamics by connecting the convergence time to the spectral gap of the adjacency matrices of underlying dynamics. This not only allows us to improve the best known upper bound, but also removes the dependency of termination time from the dimension of the ambient space. The approach adopted here can also be leveraged to connect the rate of increase of a so-called kinetic-s-energy associated with multi-agent systems to the spectral gap of their underlying dynamics. We describe a richer class of distributed systems where the agents involved in the network act in a more strategic manner. More specifically, we consider a class of resource allocation games over networks and study their evolution to some final outcomes such as Nash equilibria. We devise some simple distributed algorithms which drive the entire network to a Nash equilibrium in polynomial time for dense and hierarchical networks. In particular, we show that such games benefit from having low price of anarchy, and hence, can be used to model allocation systems which suffer from lack of coordination. This fact allows us to devise a distributed approximation algorithm within a constant gap of any pure-strategy Nash equilibrium over general networks. Subsequently we turn our attention to an important problem related to competition over social networks. We establish a hardness result for searching an equilibrium over a class of games known as competitive diffusion games, and provide some necessary conditions for existence of a pure-strategy Nash equilibrium in such games. In particular, we provide some concentration results related to the expected utility of the players over random graphs. Finally, we discuss some future directions by identifying several interesting problems and justify the importance of the underlying problems.","abstract_has_math":false,"creators":["Etesami, Seyed Rasoul"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engineering","degree_department":null,"school":null,"contributors":["Basar, Tamer","Hajek, Bruce","Srikant, Rayadurgam","Nedich, Angelia","Olshevsky, Alex"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-03-02T19:34:05Z","date_published":"2016-03-02T19:34:05Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Game Theory","Potential Theory","Social Networks","Distributed Control","Multi-agent Systems","Resource Allocation","Consensus","Opinion Dynamics","Computational Complexity","Rate of Convergence","Lyapunov function"],"languages":["en"],"rights":["Copyright 2015 Seyed Rasoul Etesami"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/89028","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Basar, Tamer","Hajek, Bruce","Srikant, Rayadurgam","Nedich, Angelia","Olshevsky, Alex"]},{"key":"dc:creator","label":"Author","values":["Etesami, Seyed Rasoul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-03-02T19:34:05Z","2015-12-02","2015-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Game Theory","Potential Theory","Social Networks","Distributed Control","Multi-agent Systems","Resource Allocation","Consensus","Opinion Dynamics","Computational Complexity","Rate of Convergence","Lyapunov function"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Seyed Rasoul Etesami"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/89028"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In recent years, there has been a wide range of studies on the role of social and distributed networks in various disciplinary areas. In particular, availability of large amounts of data from online social networks and advances in control of distributed systems have drawn the attention of many researchers to exploit the connection between evolutionary behaviors in social, communication and distributed networks. In this thesis, we first revisit several well-known types of social and distributed networks and review some relevant results from the literature. Building on this, we present a set of new results related to four different types of problems, and identify several directions for future research. The study undertaken and the approaches adopted allow us to analyze the evolution of certain types of social and distributed networks and also to identify local and global patterns of their dynamics using some novel potential-theoretic techniques. Following the introduction and preliminaries, we focus on analyzing a specific type of distributed algorithm for quantized consensus known as an unbiased quantized algorithm where a set of agents interact locally in a network in order to reach a consensus. We provide tight expressions for the expected convergence time of such dynamics over general static and time-varying networks. Following this, we introduce new protocols using a special class of Markov chains known as Metropolis chains and obtain the fastest (as of today) randomized quantized consensus protocol. The bounds provided here considerably improve the state of the art over static and dynamic networks. We make a bridge between two classes of problems, namely distributed control problems and game problems. We analyze a class of distributed averaging dynamics known as Hegselmann-Krause opinion dynamics. Modeling such dynamics as a non-cooperative game problem, we elaborate on some of the evolutionary properties of such dynamics. In particular, we answer an open question related to the termination time of such dynamics by connecting the convergence time to the spectral gap of the adjacency matrices of underlying dynamics. This not only allows us to improve the best known upper bound, but also removes the dependency of termination time from the dimension of the ambient space. The approach adopted here can also be leveraged to connect the rate of increase of a so-called kinetic-s-energy associated with multi-agent systems to the spectral gap of their underlying dynamics. We describe a richer class of distributed systems where the agents involved in the network act in a more strategic manner. More specifically, we consider a class of resource allocation games over networks and study their evolution to some final outcomes such as Nash equilibria. We devise some simple distributed algorithms which drive the entire network to a Nash equilibrium in polynomial time for dense and hierarchical networks. In particular, we show that such games benefit from having low price of anarchy, and hence, can be used to model allocation systems which suffer from lack of coordination. This fact allows us to devise a distributed approximation algorithm within a constant gap of any pure-strategy Nash equilibrium over general networks. Subsequently we turn our attention to an important problem related to competition over social networks. We establish a hardness result for searching an equilibrium over a class of games known as competitive diffusion games, and provide some necessary conditions for existence of a pure-strategy Nash equilibrium in such games. In particular, we provide some concentration results related to the expected utility of the players over random graphs. Finally, we discuss some future directions by identifying several interesting problems and justify the importance of the underlying problems.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms","The student, Seyed Rasoul Etesami, accepted the attached license on 2015-11-30 at 17:12.","The student, Seyed Rasoul Etesami, submitted this Dissertation for approval on 2015-11-30 at 17:31.","This Dissertation was approved for publication on 2015-12-02 at 08:07.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8881 on 2016-03-02 at 12:50:47","Made available in DSpace on 2016-03-02T19:34:05Z (GMT). No. of bitstreams: 2 ETESAMI-DISSERTATION-2015.pdf: 3241013 bytes, checksum: ba0ca7233004c5a960f583a48f244f50 (MD5) LICENSE.txt: 4217 bytes, checksum: cb541990d6b775d712d143dffcf7d4cd (MD5) Previous issue date: 2015-12-02"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Potential-based analysis of social, communication, and distributed networks"]}]}],"canonical_facts":{"dc:contributor":["Basar, Tamer","Hajek, Bruce","Srikant, Rayadurgam","Nedich, Angelia","Olshevsky, Alex"],"dc:creator":["Etesami, Seyed Rasoul"],"dc:date":["2016-03-02T19:34:05Z","2015-12-02","2015-12"],"dc:description":["In recent years, there has been a wide range of studies on the role of social and distributed networks in various disciplinary areas. In particular, availability of large amounts of data from online social networks and advances in control of distributed systems have drawn the attention of many researchers to exploit the connection between evolutionary behaviors in social, communication and distributed networks. In this thesis, we first revisit several well-known types of social and distributed networks and review some relevant results from the literature. Building on this, we present a set of new results related to four different types of problems, and identify several directions for future research. The study undertaken and the approaches adopted allow us to analyze the evolution of certain types of social and distributed networks and also to identify local and global patterns of their dynamics using some novel potential-theoretic techniques. Following the introduction and preliminaries, we focus on analyzing a specific type of distributed algorithm for quantized consensus known as an unbiased quantized algorithm where a set of agents interact locally in a network in order to reach a consensus. We provide tight expressions for the expected convergence time of such dynamics over general static and time-varying networks. Following this, we introduce new protocols using a special class of Markov chains known as Metropolis chains and obtain the fastest (as of today) randomized quantized consensus protocol. The bounds provided here considerably improve the state of the art over static and dynamic networks. We make a bridge between two classes of problems, namely distributed control problems and game problems. We analyze a class of distributed averaging dynamics known as Hegselmann-Krause opinion dynamics. Modeling such dynamics as a non-cooperative game problem, we elaborate on some of the evolutionary properties of such dynamics. In particular, we answer an open question related to the termination time of such dynamics by connecting the convergence time to the spectral gap of the adjacency matrices of underlying dynamics. This not only allows us to improve the best known upper bound, but also removes the dependency of termination time from the dimension of the ambient space. The approach adopted here can also be leveraged to connect the rate of increase of a so-called kinetic-s-energy associated with multi-agent systems to the spectral gap of their underlying dynamics. We describe a richer class of distributed systems where the agents involved in the network act in a more strategic manner. More specifically, we consider a class of resource allocation games over networks and study their evolution to some final outcomes such as Nash equilibria. We devise some simple distributed algorithms which drive the entire network to a Nash equilibrium in polynomial time for dense and hierarchical networks. In particular, we show that such games benefit from having low price of anarchy, and hence, can be used to model allocation systems which suffer from lack of coordination. This fact allows us to devise a distributed approximation algorithm within a constant gap of any pure-strategy Nash equilibrium over general networks. Subsequently we turn our attention to an important problem related to competition over social networks. We establish a hardness result for searching an equilibrium over a class of games known as competitive diffusion games, and provide some necessary conditions for existence of a pure-strategy Nash equilibrium in such games. In particular, we provide some concentration results related to the expected utility of the players over random graphs. Finally, we discuss some future directions by identifying several interesting problems and justify the importance of the underlying problems.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms","The student, Seyed Rasoul Etesami, accepted the attached license on 2015-11-30 at 17:12.","The student, Seyed Rasoul Etesami, submitted this Dissertation for approval on 2015-11-30 at 17:31.","This Dissertation was approved for publication on 2015-12-02 at 08:07.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8881 on 2016-03-02 at 12:50:47","Made available in DSpace on 2016-03-02T19:34:05Z (GMT). No. of bitstreams: 2 ETESAMI-DISSERTATION-2015.pdf: 3241013 bytes, checksum: ba0ca7233004c5a960f583a48f244f50 (MD5) LICENSE.txt: 4217 bytes, checksum: cb541990d6b775d712d143dffcf7d4cd (MD5) Previous issue date: 2015-12-02"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/89028"],"dc:language":["en"],"dc:rights":["Copyright 2015 Seyed Rasoul Etesami"],"dc:subject":["Game Theory","Potential Theory","Social Networks","Distributed Control","Multi-agent Systems","Resource Allocation","Consensus","Opinion Dynamics","Computational Complexity","Rate of Convergence","Lyapunov function"],"dc:title":["Potential-based analysis of social, communication, and distributed networks"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:32Z"}