CSE 522
Algorithmic and Economic Aspects of the Internet





       Structure of social networks

o       Examples of social networks: friendship graphs, scientific collaboration graphs, web graph, Internet (inter/intra domain) graph

o       Power law degree distribution

o       Small world phenomenon

o       Clustering coefficient

o       Structure of the web graph


       Models for social networks

o       Erdos-Renyi random graphs

o       Random graphs with a fixed degree distribution

o       Preferential attachment

o       Copying models

o       Models for small-world networks

o       Network formation games


       Link analysis algorithms

o       Crawling the web

o       Ranking search results: HITS (Hubs and Authorities)

o       Ranking search results: Page Rank

o       Computing Page Rank

o       Web spam

o       Axiomatic approaches to Page Rank

o       Rank aggregation and voting theory

o       Finding communities using spectral clustering


       Economic aspects of the Internet

o       Peering relations on the Internet

o       Payment-based mechanisms for routing

         path auctions

         multicast cost sharing

o       Incentive issues in P2P networks


       Topics motivated by e-commerce

o       Reputation mechanisms

o       Recommendation systems

o       Ad auctions

         Google/Overture ad auctions

         Auctions for budget-constrained bidders

         Auctions with unknown supply


       Other topics

o       Spread of viruses on social networks