In online communities, users frequently interact with strangers in order to buy and sell products, watch videos, educating themselves, and playing games. Establishing trust among strangers is essential for the functionality of these communities but challenging, as well. Online reputation systems effectively establish trust among strangers by aggregating the history of user interactions in one reputation value per user. They differ from their offline counterparts in their large number of participants spread around the world, their explicit design, and the variety of defector strategies. This thesis studies reputation systems for decentralized networks such as distributed online social networks, online markets on mobile devices, and P2P networks. Due to the highly dynamic behavior of users and the scarcity of resources, several challenging scalability and security issues arise. To face these challenges, this thesis explores algorithms that exploit the graph structure induced by the user interactions in decentralized reputation systems. The socially rich available information of online communities allows the analysis of user behavior and its evolution over time. Using the key insights of this analysis, scalable and effective algorithms are designed in order to collect, store and aggregate information in decentralized reputation systems.