Differential Privacy (DP) provides a mathematical framework to ensure privacy for individuals when their data is collected into large databases and used in various applications. In this project, we study novel extensions and aspects of DP. In one line of work, motivated by recommendation and other services in online social networks, we are trying to develop differentially private algorithms on graphs, which would still provide high accuracy/user satisfaction. In another line of work, we broaden the scope of differential privacy by developing alternate notions of accuracy and privacy.