Nowadays people and organizations are more and more interconnected in the forms of social networks: the nodes are social entities and the links are various relationships among them. The social network theory and the methods of social network analysis (SNA) are being increasingly used to study such real-world networks in order to support knowledge management and decision making in organizations. However, most existing social network studies focus on the static topologies of networks. The dynamic network link formation process is largely ignored. This dissertation is devoted to study such dynamic network formation process to support knowledge management and decision making in networked environments. Three challenges remain to be addressed in modeling and analyzing the dynamic network link formation processes. The first challenge is about modeling the network topological changes using longitudinal network data. The second challenge is concerned with examining factors that influence formation of links among individuals in networks. The third challenge is regarding link prediction in evolving social networks. This dissertation presents four essays that address these challenges in various knowledge management domains. The first essay studies the topological changes of a major international terrorist network over a 14-year period. In addition, this paper used a simulation approach to examine this network's vulnerability to random failures, targeted attacks, and real world authorities' counterattacks. The second essay and third essay focuses on examining determinants that significantly influence the link formation processes in social networks. The second essay found that mutual acquaintance and vehicle affiliations facilitate future co-offending link formation in a real-world criminal network. The third essay found that homophily in programming language preference, and mutual are determinants for forming participation links in an online Open Source social network. The fourth essay focuses on the link prediction in evolving social networks. It proposes a novel infrastructure for describing and utilizing the discovered determinants of link formation process (i.e. semantics of social networks) in link prediction to support expert recommendation application in an Open Source developer community. It is found that the integrated mechanism outperforms either user-based or Top-N most recognized mechanism.

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 tradeoffs between equilibrium networks and efficient networks.