Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Socially-based networks are of particular interest amongst the variety of communication networks arising in reality. They are distinguished by having small average path length and high clustering coefficient, and so are examples of small-world networks. This thesis studies both real examples and theoretical models of small-world networks, with particular attention to average path length. Existing models of small-world networks, due to Watts and Strogatz (1998) and Newman and Watts (1999a), impose boundary conditions on a one dimensional lattice, and rewire links locally and probabilistically in the former or probabilistically adding extra links in the latter. These models are investigated and compared with real-world networks. We consider a model in which randomness is provided by the Erdos-Rényi random network models superposed on a deterministic one dimensional structured network. We reason about this model using tools and results from random graph theory. Given a disordered network C(n, p) formed by adding links randomly with probability p to a one dimensional network C(n). We improve the analytical result regarding the average path length by showing that the onset of smallworld behaviour occurs if pn is bounded away from zero. Furthermore, we show that when pn tends to zero, C(n, p) is no longer small-world. We display that the average path length in this case approaches infinity with the network order. We deduce that at least εn (where ε is a constant bigger than zero) random links should be added to a one dimensional lattice to ensure average path length of order log n. / AFRIKAANSE OPSOMMING: Sosiaal-baseerde netwerke is van besondere belang onder die verskeidenheid kommunikasie netwerke. Hulle word onderskei deur ’n klein gemiddelde skeidingsafstand en hoë samedrommingskoëffisiënt, en is voorbeelde van kleinwêreld netwerke. Hierdie verhandeling bestudeer beide werklike voorbeelde en teoretiese modelle van klein-wêreld netwerke, met besondere aandag op die gemiddelde padlengte. Bestaande modelle van klein-wêreld netwerke, te danke aan Watts en Strogatz (1998) en Newman en Watts (1999a), voeg randvoorwaardes by tot eendimensionele roosters, en herbedraad nedwerkskakels gebaseer op lokale kennis in die eerste geval en voeg willekeurig ekstra netwerkskakels in die tweede. Hierdie modelle word ondersoek en vergelyk met werklike-wêreld netwerke. Ons oorweeg ’n prosedure waarin willekeurigheid verskaf word deur die Erdös- Renyi toevalsnetwerk modelle wat op ’n een-dimensionele deterministiese gestruktureerde netwerk geimposeer word. Ons redeneer oor hierdie modelle deur gebruik te maak van gereedskap en resultate toevalsgrafieke teorie. Gegewe ’n wanordelike netwerk wat gevorm word deur skakels willekeurig met waarskynlikheid p tot ‘n een-dimensionele netwerk C(n) toe te voeg, verbeter ons die analitiese resultaat ten opsigte van die gemiddelde padlengte deur te wys dat die aanvang van klein-wêreld gedrag voorkom wanneer pn weg van nul begrens is. Verder toon ons dat, wanneer pn neig na nul, C(n, p) nie meer klein-wêreld is nie. Ons toon dat die gemiddelde padlengte in hierdie geval na oneindigheid streef saam met die netwerk groote. Ons lei af dat ten minste εn (waar εn n konstante groter as nul is) ewekansige skakels bygevoeg moet word by ’n een-dimensionele rooster om ‘n gemiddelde padlengte van orde log n te verseker.

It has been observed that real-world random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closely-knit groups that are locally dense and globally sparse. These closely-knit 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 community-discovery 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 community-discovery algorithms is their computational complexity. These algorithms do not scale up to the enormous size of the real-world networks. We propose a hash-table-based 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 five-year period. Our results show super-linear 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.

First and foremost, I would like to extend my deepest gratitude to my advisor, Professor Narsingh Deo, for his excellent guidance and encouragement, and also for introducing me to this wonderful science of complex networks. Without his support this dissertation would not have been possible. I would also like to thank the members of my research committee, professors Charles Hughes, Ratan Guha, Mainak Chatterjee and Yue Zhao for their advice and guidance during the entire process. I am indebted to the faculty and the staff of the Department of Electrical Engineering and Computer Science for providing me the resources and environment to perform this research. I am grateful to my colleagues in the Parallel and Quantum computing lab for the stimulating discussions and support. I would also like to thank Dr. Hemant Balakrishnan and Dr. Sanjeeb Nanda for their valuable suggestions and guidance. My heartfelt thanks to my parents, Vasudevan and Raji, who have always been supportive of my decisions and encouraged me with their best wishes. I would also like to thank my sister Gomathy, for her words of care and affection during tough times. Special thanks to my friends in Orlando for being there when I needed them

In nature, many social species demonstrate collective behavior ranging from coordinated motion in flocks of birds and schools of fish to collective decision making in humans. Such distinct behavioral patterns at the group level are the consequence of local interactions among the individuals. We can learn from these biological systems, which have successfully evolved to operate in noisy and fault-prone environments, and understand how these complex interactions can be applied to engineered systems where robustness remains a major challenge. This dissertation addresses a two-scale approach to study these interactions- one in larger scale, where we are interested in the information exchange in a group and how it enables the group to reach a common decision, and the other in a smaller scale, where we are focused in the presence and directionality in the information exchange in a pair of individuals. To understand the interactions at large scale, we use a graph theoretic approach to study consensus or synchronization protocols over two types of biologically-inspired interaction networks. The first network captures both collaborative and antagonistic interactions and the second considers the impact of dynamic leaders in presence of purely collaborative interactions. To study the interactions at small scale, we use an information theoretic approach to understand the directionality of information transfer in a pair of individual using a real-world data-set of animal group motion. Finally, we choose the issue of same-sex marriage in the United States to demonstrate that collective opinion formation is not only a result of negotiations among the individuals, but also reflects inherent spatial and political similarities and temporal delays. / Ph. D.

Braess' paradox is a counter-intuitive phenomenon which can occur in congesting networks. It refers to those cases where the introduction of a new link in the network results in the total travel time on the network increasing. The dissertation starts by introducing the traffic assignment problem and the concept of equilibrium in traffic assignment. The concept of equilibrium is based on Wardrop's first principle that all travellers will attempt to minimize their own travel time regardless of the effect on others. A literature review includes details of a number of papers that have been published investigating theoretical aspects of the paradox. There is also a brief description of Game Theory and the Nash Equilibrium. It has been shown that the equilibrium assignment is an example of Nash Equilibrium. The majority of work that has been published deals with networks where the delay functions that are used to compute the travel times on the links of the network do not include explicit representation of the capacity of the links. In this dissertation a network that is similar in form to the one first presented by Braess was constructed with the difference being that the well-known BPR function was used in the delay functions. This network was used to show that a number of findings that had been presented previously using simpler functions also applied to this network. It was shown that when it occurs, Braess' paradox only occurs over a range of values at relatively low levels of congestion. Real-world networks were then investigated and it was found that similar results occurred to those found in the simpler test networks that are often used in discussions of the paradox. Two methodologies of eliminating the paradox were investigated and the results are presented. / Decision Sciences / M.Sc.

Braess' paradox is a counter-intuitive phenomenon which can occur in congesting networks. It refers to those cases where the introduction of a new link in the network results in the total travel time on the network increasing. The dissertation starts by introducing the traffic assignment problem and the concept of equilibrium in traffic assignment. The concept of equilibrium is based on Wardrop's first principle that all travellers will attempt to minimize their own travel time regardless of the effect on others. A literature review includes details of a number of papers that have been published investigating theoretical aspects of the paradox. There is also a brief description of Game Theory and the Nash Equilibrium. It has been shown that the equilibrium assignment is an example of Nash Equilibrium. The majority of work that has been published deals with networks where the delay functions that are used to compute the travel times on the links of the network do not include explicit representation of the capacity of the links. In this dissertation a network that is similar in form to the one first presented by Braess was constructed with the difference being that the well-known BPR function was used in the delay functions. This network was used to show that a number of findings that had been presented previously using simpler functions also applied to this network. It was shown that when it occurs, Braess' paradox only occurs over a range of values at relatively low levels of congestion. Real-world networks were then investigated and it was found that similar results occurred to those found in the simpler test networks that are often used in discussions of the paradox. Two methodologies of eliminating the paradox were investigated and the results are presented. / Decision Sciences / M.Sc.