This thesis presents space-efficient algorithms to sample from random web graphs generated by two important stochastic graph models based on concept of copying: the linear copy model and the hostgraph model. The goal is to avoid constructing the entire random graph, and instead use an amount of space nearer to the desired (smaller) sample size. The efficiency of our algorithms is achieved by refraining from making unnecessary random decisions when constructing the sample. The construc- tion of a sample subgraph from a random graph with n nodes and k outgoing links on each node based on the linear copying model uses an expected O(klnn) words for each node in the sample subgraph. The construction of a sample subgraph from a random graph with n nodes based on the hostgraph model uses, for any small sample size, an expected n+o(n) words.

We look at the underlying friendships and relationships between Chinese Internet users. We identify the presence and characteristics of the different types of online friendships and online relationships by analyzing various online social networks. First, we look at the concept of guanxi as it is applied to the interaction between web sites. Guanxi is a type of dyadic social interaction based on feelings and trust which has been well studied by scholars in China. We define guanxi in the web: particular linking patterns that appear in the web as well as supporting textual evidence in the web pages which we believe are indicative of the presence and varying strengths of the underlying guanxi between Chinese web site owners. Through our empirical study of the Chinese web, the general web, and the Japanese, Iranian, and French web, we show that guanxi between web sites is a more prevalent feature in the Chinese web. Next, we study the formation of online friendships in Douban, an online social networking platform frequently used by the youth in China. We look at several factors that can affect the evolution of friendships such as having memberships in the same discussion groups and sharing common interests or common friends. We compare these factors in influencing the formation of online friendships. Our work provides the first study on the underlying relationships between web sites in the Chinese web and the first large scale empirical analysis on the evolution of friendships in a Chinese online social network.