Our proposed techniques for measurement and analysis enable us to accurately characterize fundamental properties of widely deployed OSNs. There is a great interest in these characteristics among networking researchers as well as OSN designers. There is also a great deal of interest in OSNs among social scientists because of their large size, new properties and the feasibility of collecting snapshots of the system over time. The main theme in our characterization is to {\em compare and contrast the properties of virtual and non-virtual social networks}. We use existing sociological models of non-virtual social networks as ``null hypotheses'' to characterize the observed properties and dynamics in OSNs. We then leverage our domain knowledge of networking, graph analysis, and sociology to identify the underlying social and non-social factors that generate the structural properties and evolution of OSNs. \noindent {\bf Background on OSNs:} Users are first-class objects in an OSN. The information that is associated with each user may vary across different OSNs but can be broadly divided into three categories as follows: {\em (i) User Profile}: a profile that contains a set of user attributes (\eg location, name, age), {\em (ii) Friend List}: a list of other users that are considered as friends, {\em (iii) Interactions}: one or multiple sets of interactions with other users in the system. This information for an OSN can be represented by a {\em friendship} graph and one (or several) {\em interaction} graphs. For simplicity, we refer to these as {\em f} and {\em i} graphs, respectively. The {\em f} graph represents the collection of friend lists across all users. Each node represents a user and each edge indicates friendship relationship between connected nodes. We can also attach a weight to each edge to represent the duration of the corresponding friendship (when such information is available). The profile information of individual users can also be represented as attributes of the corresponding nodes. Each {\em i} graph represents the paths of interaction (of a similar type) among users. Depending on the reciprocity of friendship or interactions, the {\em f} or {\em i} graphs would have directed or undirected connectivity. A weight could also be associated with each edge to indicate the level of interactions (\eg rate of exchanged messages) between two users. Depending on the provided features of an OSN, several types of interactions may occur between users. These interactions can be further divided into {\em direct} (\eg instant messaging, file and video exchange) and indirect (\eg fan-owner) interactions. The proposed multi-resolution analysis reveals connectivity of the {\em f} or {\em i} graphs at different scales, which enables us to explore the following fundamental issues in OSNs: \noindent {\bf Connectivity at Different Resolutions:} To study the degree and pattern of ``social cohesion'' of a given social network, social scientists focus on node connectivity by examining embedded, multi-level ``cluster-within-cluster'' structures in the network \cite{moody2003sociologicalreview}. This rather new approach to social network analysis is perfectly aligned to our proposed MRA technique. However, existing applications of this model have been restricted to single snapshots of small networks and have given relatively little attention to the structural properties of coarse-level clusters in social networks. To extend the research in this area, we examine the following research questions: Whether or not friendship graphs at different OSNs exhibit ``cluster within cluster'' structures as a signature for social cohesion? What is the level of clustering at different scales? We also explore the connectivity of the interaction graph at different scales which has received little attention in prior studies. \noindent {\bf Evolution of Connectivity \& Modeling:} A common approach to characterize the evolution of social networks is to present a hypothesis for the underlying micro-level dynamics that drive the macro-level structural properties of the network over time. The underlying micro-level dynamics can be used to model the network as well. These studies typically validate their hypotheses using simulation based on random graph modeling \cite{snijders2006sociologicalmethodology}. Because several micro-level dynamics can produce a particular macro-level property of a graph (\ie there is no one-to-one mapping between underlying causes and resulting properties), and because these studies typically rely on a single cross-section of the network, or at most a few snapshots over time, they cannot reliably nail down the specific generative factors that drive the evolution of the network \cite{4-KDD-studies}. Our multi-scale analysis enables us to separately examine the evolution of the graph at coarse and fine resolutions. Furthermore, since we collect many snapshots of the graph over time, we are able to pin point the underlying dynamics and directly characterize network evolution with longitudinal data rather than random graph simulation. In the context of the interaction graphs, we also group edges that are associated with interest to a particular content or application and their evolution over time to characterize the pattern of diffusion of content (\ie diffusion of innovation) among users over time. We leverage existing diffusion models in epidemiology and related fields \cite{burris2007diffusion} as null hypotheses to characterize evolution of interactions among users. We present a new modeling approach for OSNs that is inspired by HOT (for Highly Organized Tolerance \cite{doyle00prl,carlson99pre}) that has been recently used for modeling the Internet router and AS-level topologies \cite{li04sigcomm,doyle05pnas,alderson05ton}. The HOT approach considers engineering design and social factors rather than randomness as the main forces at work in shaping and modeling the structure and dynamics of friendship and interactions in OSNs. \noindent {\bf Similarities Between Graphs:} Comparison of two graphs at different scales of resolution reveals similarities (or differences) that are otherwise difficult to identify. In particular, we investigate the similarities between the friendship and interaction graphs of a given OSN at different scales. The comparison of friendship and interaction graphs along with their patterns of evolution that we discussed earlier, allows us to explore the mutual dependency between friendship and interactions in a target OSN. For example, this exercise demonstrates whether existing friendships trigger future interactions or vice versa. Examining the similarities between interactions (or friendship) graphs of different OSNs demonstrates to what extent their behavior is similar despite potentially important differences in various aspects of those OSNs. \noindent {\bf Predicting Missing Information:} [XXX, how MRA can be used to predict missing attributes or edges in i or f graphs] This can be used to identify an error in the measurement or as a recommendation scheme to facilitate/expedite likely interactions. [XXX, TBR] \noindent {\bf Comparing Virtual vs Non-Virtual Social Networks} Comparisons between virtual and non-virtual social networks have been primarily theoretical or anecdotal and not based on explicit empirical research \cite{wellman99communities}. We leverage an array of known graph properties of non-virtual social networks (\ie communities) to compare their connectivity with OSNs, including transitivity, reciprocity, homophily, multiplexity, durability, and hierarchy. This comparison could also reveal the unique characteristics of OSNs that are likely to be driven by technical (\ie non-social) factors, or simply a phenomenon that occurs due to the significantly larger size of OSN graphs compared to other social networks. In addition to the accuracy of measurement, we explore the role of the following non-social factors on observed properties: offered services by the target OSN (recommendation algorithm, selecting popular content), directed vs undirected connectivity, network size, any enforced limits (\eg in the number of users, posted files, interactions) by the system, starting time of offered services. For example, we would like to identify ``Whether the observed pattern of interactions in the {\em i} graph or level of clustering in the {\em f} graph in an OSN is mainly driven by social factors or by features provided by the OSN?''. Toward this end, we leverage our domain knowledge of networking, graph analysis, and sociology. \noindent {\bf Attribute-Based Analysis:} The availability of user attributes motivate the analysis of connectivity among groups with common attributes. Toward this end, we examine whether OSN exhibits {\em attribute homophily} in the formation of social ties \cite{mcpherson2001sociologyreview}, \ie whether each user tends to establish ties with other users with the same attributes. The existing theory about homophily is premised mainly on the psychological predispositions of individual actors, and thus applicable to fine scales. The multi-scale view of the graph enables us to separate and characterize the presence of homophily at fine and coarse scales.