·       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