Online social networks allow us to study the interactions between people. Typically, users share updates, photos, videos and URL with the other users they are connected to and others share their feedback by "liking", commenting or sharing the content. In our work, we study the social networks at the community level of structure of interactions and at the individual level of user influence.

(1) Community level: The social interactions can be represented as a graph. Graph decomposition techniques, such as k-core decomposition, have been used to understand structures such as partitions and hierarchies in graphs. In this work we present a 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%. 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.

(2) 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 \pm \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.