etd@IISc Collection:
http://hdl.handle.net/2005/18
Thu, 25 Dec 2014 02:26:25 GMT2014-12-25T02:26:25ZVisual Analysis Of Interactions In Multifield Scientific Data
http://hdl.handle.net/2005/2407
Title: Visual Analysis Of Interactions In Multifield Scientific Data
Authors: Suthambhara, N
Abstract: Data from present day scientific simulations and observations of physical processes often consist of multiple scalar fields. It is important to study the interactions between the fields to understand the underlying phenomena. A visual representation of these interactions would assist the scientist by providing quick insights into complex relationships that exist between the fields.
We describe new techniques for visual analysis of multifield scalar data where the relationships can be quantified by the gradients of the individual scalar fields and their mutual alignment. Empirically, gradients along with their mutual alignment have been shown to be a good indicator of the relationships between the different scalar variables.
The Jacobi set, defined as the set of points where the gradients are linearly dependent, describes the relationship between the gradient fields. The Jacobi set of two piecewise linear functions may contain several components indicative of noisy or a feature-rich dataset. For two dimensional domains, we pose the problem of simplification as the extraction of level sets and offset contours and describe a robust technique to simplify and create a multi-resolution representation of the Jacobi set.
Existing isosurface-based techniques for scalar data exploration like Reeb graphs, contour spectra, isosurface statistics, etc., study a scalar field in isolation. We argue that the identification of interesting isovalues in a multifield data set should necessarily be based on the interaction between the different fields. We introduce a variation density function that profiles the relationship between multiple scalar fields over isosurfaces of a given scalar field. This profile serves as a valuable tool for multifield data exploration because it provides the user with cues to identify interesting isovalues of scalar fields.
Finally, we introduce a new multifield comparison measure to capture relationships between scalar variables. We also show that our measure is insensitive to noise in the scalar fields and to noise in their gradients. Further, it can be computed robustly and efficiently. The comparison measure can be used to identify regions of interest in the domain where interactions between the scalar fields are significant. Subsequent visualization of the data focuses on these regions of interest leading to effective visual analysis.
We demonstrate the effectiveness of our techniques by applying them to real world data from different domains like combustion studies, climate sciences and computer graphics.Thu, 13 Nov 2014 18:30:00 GMThttp://hdl.handle.net/2005/24072014-11-13T18:30:00ZRainbow Connection Number Of Graph Power And Graph Products
http://hdl.handle.net/2005/2383
Title: Rainbow Connection Number Of Graph Power And Graph Products
Authors: Arunselvan, R
Abstract: The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.Mon, 08 Sep 2014 18:30:00 GMThttp://hdl.handle.net/2005/23832014-09-08T18:30:00ZA Novel Game Theoretic And Voting Mechanism Based Approach For Carbon Emissions Reduction
http://hdl.handle.net/2005/2361
Title: A Novel Game Theoretic And Voting Mechanism Based Approach For Carbon Emissions Reduction
Authors: Shelke, Sunil Sitaram
Abstract: Global warming is currently a major challenge facing the world. There are widespread ongoing efforts in the form of summits, conferences, etc., to find satisfactory ways of surmounting this challenge. The basic objective of all such efforts can be summarized as conception and formation of protocols to reduce the pace of global carbon levels. Game theory and mechanism design provide a natural modeling tool for capturing the strategic dynamics involved in global warming related problems. This dissertation explores for the first time the use of voting mechanisms in the context of solving the central problems, namely, allocation of emission caps and reduction quotas to strategic emitting agents (countries).
The contribution of this dissertation is two-fold. The first contribution is to develop an elegant game theoretic model that accurately captures the strategic interactions among different emitting agents in a global warming setting. This model facilitates a convenient way of exploring a mechanism design approach for solving important allocation problems in the global warming context. The second contribution is to propose and explore a novel approach, based on voting mechanisms, to solve two problems: (1) allocating emission caps and (2) allocating reduction quotas to strategic agents.
Our work investigates the use of voting mechanisms that satisfy four desirable properties:
(1) non-dictatorship, (2) strategy-proofness, (3) efficiency, and (4) anonymity. In particular, we explore the median selection, maximum order statistic selection, and general Kth order statistic selection voting mechanisms. Our results clearly show that only trivial allocations satisfy all the above properties simultaneously. We next investigate the use of voting mechanisms for the dual problem, namely, allocation of emission reductions to emitting agents. Here, we show that non-trivial allocations are possible, however an important property, individual rationality, might be compromised.
The investigations in the thesis bring out certain limitations in applying voting mechanisms that satisfy all the four properties above. Nevertheless, the insights obtained provide valuable guidelines for solving emission allocation related problems in a principled and informed way.Wed, 06 Aug 2014 18:30:00 GMThttp://hdl.handle.net/2005/23612014-08-06T18:30:00ZGame Theoretic Models For Social Network Analysis
http://hdl.handle.net/2005/2350
Title: Game Theoretic Models For Social Network Analysis
Authors: Narayanam, Ramasuri
Abstract: With increasing demand for social network based activities, it is very important to understand not only the structural properties of social networks but also how social networks form, to better exploit their promise and potential. We believe the existing methods and tools for social network analysis have a major inadequacy: they do not capture the behavior (such as rationality and intelligence) of individuals nor do they model the strategic interactions that occur among these individuals. Game theory is a natural tool to overcome this inadequacy since it provides rigorous mathematical models of strategic interaction among autonomous, intelligent, and rational agents. This thesis brings out how a game theoretic approach helps analyze social networks better. In particular, we study three contemporary and pertinent problems in social networks using a game theoretic approach: determining influential individuals for viral marketing, community detection, and social network formation.
The first problem deals with determining influential nodes in social networks for diffusion of information. We present an efficient heuristic algorithm (SPIN) to this problem based on cooperative game theoretic techniques. The running time of SPIN is independent of the number of influential nodes to be determined. Moreover, unlike the popular benchmark algorithms, the proposed method works well with both submodular and non-submodular objective functions for diffusion of information.
In the second problem, we design a novel game theoretic approach to partition a given undirected, unweighted graph into dense subgraphs (or communities). The approach is based on determining a Nash stable partition which is a pure strategy Nash equilibrium of an appropriately defined strategic form game. In the proposed graph partitioning game, the nodes of the graph are the players and the strategy of a node is to decide to which community it ought to belong. The utility of each node is defined to depend entirely on the node’s local neighborhood. A Nash stable partition (NSP) of this game is a partition consisting of communities such that no node has incentive to defect from its community to any other community. Given any graph, we prove that an NSP always exists and we also derive a lower bound on the fraction of intra-community edges in any NSP. Our approach leads to an efficient heuristic algorithm to detect communities in social networks with the additional feature of automatically determining the number of communities.
The focus of the third problem is to understand the patterns behind the evolution of social networks that helps in predicting the likely topologies of social networks. The topology of social networks plays a crucial role in determining the outcomes in several social and economic situations such as trading networks, recommendation networks. We approach the problem of topology prediction in networks by defining a game theoretic model, which we call value function -allocation rule model, that considers four determinants of network formation. This model uses techniques from both cooperative game theory and non-cooperative game theory. We characterize the topologies of networks that are in equilibrium and/or socially efficient. Finally, we study the tradeoﬀs between equilibrium networks and efficient networks.Thu, 31 Jul 2014 18:30:00 GMThttp://hdl.handle.net/2005/23502014-07-31T18:30:00Z