CSE 522
Algorithmic and Economic Aspects of the Internet



General

Syllabus

Lectures

Links


       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