Characterization and re-identification of roles in Connection Networks

• Larissa Pinheiro Spinelli UFRJ
• Daniel R. Figueiredo UFRJ

Abstract

Connection Networks are an abstraction to model the exchange of information between entities. In this abstraction, entities are represented by vertices and the exchange of information between two entities is represented by edges. Entities in Connection Networks can have distinct roles which can be related to their functionality. For example, in the Internet Connection Network, entities represented by IP addresses can play the role of client or server. However, many Connection Networks are anonymized in order to omit information concerning the identity and the role of the entities. This paper presents a study of the structural characteristics of the Internet Connection Network as well as a characterization of the different roles played by vertices. Using this characterization, this work proposes techniques to re-identify the role of vertices in anonymized Internet Connection Networks. These techniques use only the structural properties of the network. Finally, the proposed techniques are evaluated and compared to assess their efficiency in re-identifying roles. Numerical results are very promising and indicate that it is possible to re-identify roles with a success rate of over 96%.

References

Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Mod. Phys., 74(1):47–97.

Baeza-Yates, R. and Ribeiro-Neto, B. (1999). Modern Information Retrieval. Addison Wesley.

Colby Walsworth, Emile Aben, k. c. D. A. (2009). The caida anonymized 2009 internet traces - ¡dates used¿.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to Algorithms, Second Edition. McGraw-Hill Science/Engineering/Math.

Hay, M., Miklau, G., Jensen, D., Towsley, D. F., and Weis, P. (2008). Resisting structural re-identification in anonymized social networks. VLDB, 1(1):102–114.

Hay, M. and Srivastava, S. (2006). Privacy and anonymity in graph data.

Iliofotou, M., Pappu, P., Faloutsos, M., Mitzenmacher, M., Singh, S., and Varghese, G. (2007). Network monitoring using traffic dispersion graphs (tdgs). In Proceedings of the 7th ACM SIGCOMM Internet Measurement Conference, pages 315–320, New York, NY, USA. ACM.

Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., and Makse, H. A. (2010). Identifying influential spreaders in complex networks. cite arxiv:1001.5285 Comment: 31 pages, 12 figures.

Mahadevan, P., Krioukov, D., Dimitropoulos, X., Huffaker, B., Fomenkov, M., kc claffy, and Vahdat, A. The internet as-level topology: Three data sources and one definitive metric.

Meiss, M., Menczer, F., and Vespignani, A. (2005). On the lack of typical behavior in the global web traffic network. In WWW ’05: Proceedings of the 14th international conference on World Wide Web, pages 510–518, New York, NY, USA. ACM.

Narayanan, A. and Shmatikov, V. (2009). De-anonymizing social networks. Security and Privacy, IEEE Symposium on, 0:173–187.

Pang, R., Allman, M., Paxson, V., and Lee, J. (2006). The devil and packet trace anonymization. SIGCOMM Comput. Commun. Rev., 36(1):29–38.