DescriptionStructure 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, k-core decomposition has been used in many applications to find dense regions in a graph. We present a space efficient approximate algorithm to compute k-core decomposition using O(n log d) space approximate algorithm to estimate k-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 k-core, k-peak decomposition finds centers of dense regions in a graph. We present analysis of the k-peak decomposition and show that it outperforms k-core decomposition in applications such as community detection. In addition to that, we present a graph visualization technique, that uses both k-core and k-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 ± ε) 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.