|
Abstract:
|
Scalable and accurate analysis of networks is essential to a wide variety of existing and emerging network systems . Specifically , network measurement and analysis helps to understand networks , improve existing services , and enable new data -mining applications . To support various services and applications in large -scale networks , network analytics must address the following challenges : (i ) how to conduct scalable analysis in networks with a large number of nodes and links , (ii ) how to flexibly accommodate various objectives from different administrative tasks , (iii ) and how to cope with the dynamic changes in the networks . This dissertation presents novel path analysis schemes that effectively address the above challenges in analyzing pair -wise relationships among networked entities . In doing so , we make the following three major contributions to large -scale IP networks , social networks , and application service networks . For IP networks , we propose an accurate and flexible framework for path property monitoring . Analyzing the performance side of paths between pairs of nodes , our framework incorporates approaches that perform exact reconstruction of path properties as well as approximate reconstruction . Our framework is highly scalable to design measurement experiments that span thousands of routers and end hosts . It is also flexible to accommodate a variety of design requirements . For social networks , we present scalable and accurate graph embedding schemes . Aimed at analyzing the pair -wise relationships of social network users , we present three dimensionality reduction schemes leveraging matrix factorization , count -min sketch , and graph clustering paired with spectral graph embedding . As concrete applications showing the practical value of our schemes , we apply them to the important social analysis tasks of proximity estimation , missing link inference , and link prediction . The results clearly demonstrate the accuracy , scalability , and flexibility of our schemes for analyzing social networks with millions of nodes and tens of millions of links . For application service networks , we provide a proactive service quality assessment scheme . Analyzing the relationship between the satisfaction level of subscribers of an IPTV service and network performance indicators , our proposed scheme proactively (i .e . , detect issues before IPTV subscribers complain ) assesses user -perceived service quality using performance metrics collected from the network . From our evaluation using network data collected from a commercial IPTV service provider , we show that our scheme is able to predict 60 % of the service problems that are complained by customers with only 0 .1 % of false positives . |