| Structure of social connections and interpersonal dynamics based on user behavior shapes the culture, politics and economics of the world. Building consumer products and services, require a good understanding of the human social behavior, computational tools to analyze it and efficient techniques to model and predict it.;In this dissertation we study the graph structure of interactions at the community level and the social influence between users at an individual level in a social network. Our contributions are in the form of efficient algorithms, theoretical and experimental analysis and visualizations.;At the community level, kappa-core decomposition has been used in many applications to find dense regions in a graph. We present a space efficient approximate algorithm to compute kappa-core decomposition using O(eta log d) space approximate algorithm to estimate kappa-cores in graphs, where n is the number of nodes, and d is the maximum degree. Our experimental study shows space savings up to 60X with average relative error less than 2.3% as compared to the in-memory method. Analogous to kappa-core, kappa-peak decomposition finds centers of dense regions in a graph. We present analysis of the kappa-peak decomposition and show that it outperforms kappa-core decomposition in applications such as community detection. In addition to that, we present a graph visualization technique, that uses both kappa-core and kappa-peak decomposition to give a global mapping of the graph.;At the individual level, we study the influence of users on one another based on the posts they share and the feedback received. H-index, used as a measure of impact in academic settings, can also be used as a measure of influence in online social interactions. The high volume and rate of online social interactions make in-memory computations challenging. We present algorithms to compute h-index in various streaming settings and get a (1 +/- epsilon) estimate of the h-index with sublinear, ie, polylog or even O(1) space.;Thus, we present efficient algorithms, analysis and visualizations in an effort to study the group level structure of interactions and individual level influence, among users in social networks. |
