T. Abdssalem and I. B. Dhia, A reachability-based access control model for online social networks, Databases and Social Networks on, DBSocial '11, 2011.
DOI : 10.1145/1996413.1996419

D. Imen-ben, Access Control in Social Networks : A reachability-Based Approach, Joint EDBT/ICDT Ph.D. Workshop, 2012.

T. Imen-ben-dhia, M. Abdssalem, and . Sozio, Primates, Proceedings of the 21st ACM international conference on Information and knowledge management, CIKM '12, 2012.
DOI : 10.1145/2396761.2398748

T. Imen-ben-dhia, M. Abdssalem, and . Sozio, Primates, Proceedings of the 21st ACM international conference on Information and knowledge management, CIKM '12, 2013.
DOI : 10.1145/2396761.2398748

T. Imen-ben-dhia, M. Abdssalem, and . Sozio, EUQLID: Efficient Distance Queries in Large Directed Graphs. Under review

E. References, [. Agrawal, A. Borgida, and H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, SIGMOD Rec, pp.253-262, 1989.

C. Akcora, B. Carminati, and E. Ferrari, Privacy in Social Networks: How Risky is Your Social Graph?, 2012 IEEE 28th International Conference on Data Engineering, pp.9-19, 2012.
DOI : 10.1109/ICDE.2012.99

T. Abdessalem, B. Cautis, and A. Souihli, Trust management in social networks, 2009.

M. Atre, V. Chaoji, and M. J. Zaki, Bitpath ? label order constrained reachability queries over large graphs, 1203.

T. Abdessalem and I. B. Dhia, A reachability-based access control model for online social networks, Databases and Social Networks on, DBSocial '11, pp.31-36, 2011.
DOI : 10.1145/1996413.1996419

P. Noga-alon, I. Dao, F. Hajirasouliha, S. Hormozdiari, and . Sahinalp, Biomolecular network motif counting and discovery by color coding, Bioinformatics, pp.241-249, 2008.

I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway dimension, shortest paths, and provably efficient algorithms. SODA, pp.782-793, 2010.

F. Ada, W. Huanhuan, W. Cheng, and . Raymond, Is-label: an independentset based labeling scheme for point-to-point distance querying, 2013.

A. Barabasi, Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life, 2003.

P. Boldi and F. Bonchi, Aristides Gionis, and Tamir Tassa Injecting uncertainty in graphs for identity obfuscation, Proc. VLDB Endow, pp.1376-1387, 2012.

[. Bramandia, B. Choi, and W. Ng, On incremental maintenance of 2-hop labeling of graphs, Proceeding of the 17th international conference on World Wide Web , WWW '08, pp.845-854, 2008.
DOI : 10.1145/1367497.1367611

M. Danah, N. B. Boyd, and . Ellison, Social network sites: Definition, history, and scholarship, Journal of Computer-Mediated Communication, issue.11, 2007.

J. E. Bartlett, J. W. Kotrlik, and C. C. Higgins, Organizational research: Determining appropriate sample size in survey research, Information Technology, Learning, and Performance Journal, vol.19, 2001.

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, R. Sridhar-rajagopalan et al., Graph structure in the Web, Computer Networks, vol.33, issue.1-6, pp.309-320, 2000.
DOI : 10.1016/S1389-1286(00)00083-9

S. Peter, J. Bearman, K. Moody, and . Stovel, Chains of affection: The structure of adolescent romantic and sexual networks, American Journal of Sociology, pp.44-91, 2002.

B. Berger, J. Rompel, and P. W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, 30th Annual Symposium on Foundations of Computer Science, pp.454-477, 1994.
DOI : 10.1109/SFCS.1989.63455

P. Boldi, M. Rosa, M. Santini, and S. Vigna, Layered label propagation, Proceedings of the 20th international conference on World wide web, WWW '11, 2011.
DOI : 10.1145/1963405.1963488

P. Boldi and S. Vigna, Four Degrees of Separation, Really, 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp.1222-1227, 2012.
DOI : 10.1109/ASONAM.2012.211

Y. Chen and Y. Chen, An Efficient Algorithm for Answering Graph Reachability Queries, 2008 IEEE 24th International Conference on Data Engineering, pp.893-902, 2008.
DOI : 10.1109/ICDE.2008.4497498

S. Chu and J. Cheng, Triangle listing in massive networks, ACM Transactions on Knowledge Discovery from Data, vol.6, issue.4, pp.1-1732, 2012.
DOI : 10.1145/2382577.2382581

B. Carminati, E. Ferrari, and A. Perego, Enforcing access control in Web-based social networks, ACM Transactions on Information and System Security, vol.13, issue.1, pp.1-638, 2009.
DOI : 10.1145/1609956.1609962

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, Reachability and distance queries via 2-hop labels. SODA, pp.937-946, 2002.

J. Cheng, S. Huang, H. Wu, and A. Fu, TF-Label, Proceedings of the 2013 international conference on Management of data, SIGMOD '13, pp.193-204, 2013.
DOI : 10.1145/2463676.2465286

J. Cheng, Y. Ke, S. Chu, and C. Cheng, Efficient processing of distance queries in large graphs, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, pp.457-468, 2012.
DOI : 10.1145/2213836.2213888

G. Cormode, H. Karloff, and A. Wirth, Set cover algorithms for very large datasets, Proceedings of the 19th ACM international conference on Information and knowledge management, CIKM '10, pp.479-488, 2010.
DOI : 10.1145/1871437.1871501

J. Cai and C. Keung-poon, Path-hop, Proceedings of the 19th ACM international conference on Information and knowledge management, CIKM '10, pp.119-128, 2010.
DOI : 10.1145/1871437.1871457

J. Cheng, Z. Shang, H. Cheng, H. Wang, J. Xu et al., K-reach, Proc. VLDB Endow, pp.1292-1303, 2012.
DOI : 10.14778/2350229.2350247

J. Cheng, J. Xu, and Y. , On-line exact shortest distance query processing, Proceedings of the 12th International Conference on Extending Database Technology Advances in Database Technology, EDBT '09, pp.481-492, 2009.
DOI : 10.1145/1516360.1516417

J. Cheng, X. Xu-yu, H. Lin, P. S. Wang, and . Yu, Fast Computation of Reachability Labeling for Large Graphs, pp.961-979, 2006.
DOI : 10.1007/11687238_56

J. Cheng, X. Xu-yu, H. Lin, P. S. Wang, and . Yu, Fast computing reachability labelings for large graphs with high compression rate, Proceedings of the 11th international conference on Extending database technology Advances in database technology, EDBT '08, 2008.
DOI : 10.1145/1353343.1353370

D. Chakrabarti, Y. Zhan, and C. Faloutsos, R-MAT: A Recursive Model for Graph Mining, SIAM, 2004.
DOI : 10.1137/1.9781611972740.43

G. Danezis, Inferring privacy policies for social networking services, Proceedings of the 2nd ACM workshop on Security and artificial intelligence, AISec '09, 2009.
DOI : 10.1145/1654988.1654991

T. Imen-ben-dhia, M. Abdessalem, and . Sozio, Primates, Proceedings of the 21st ACM international conference on Information and knowledge management, CIKM '12, pp.2746-2748, 2012.
DOI : 10.1145/2396761.2398748

. W. Edsger and . Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol.1, pp.269-271, 1959.

P. Erdos and A. Rényi, On the evolution of random graphs, PUBLICATION OF THE MATHEMATICAL INSTITUTE OF THE HUNGARIAN ACADEMY OF SCIENCES, pp.17-61, 1960.

[. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the internet topology, SIGCOMM, pp.251-262, 1999.

L. Fang and K. Lefevre, Privacy wizards for social networking sites, Proceedings of the 19th international conference on World wide web, WWW '10, 2010.
DOI : 10.1145/1772690.1772727

G. William-flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, Self-organization and identification of web communities, Computer, pp.66-71, 2002.

E. Fan, J. Li, S. Ma, N. Tang, and Y. Wu, Adding regular expressions to graph reachability and pattern queries, 2011 IEEE 27th International Conference on Data Engineering, pp.39-50, 2011.
DOI : 10.1109/ICDE.2011.5767858

L. Michael, R. E. Fredman, and . Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, pp.596-615, 1987.

A. Gubichev, S. J. Bedathur, S. Seufert, and G. Weikum, Fast and accurate estimation of shortest paths in large graphs, Proceedings of the 19th ACM international conference on Information and knowledge management, CIKM '10, 2010.
DOI : 10.1145/1871437.1871503

M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, Walking in Facebook: A Case Study of Unbiased Sampling of OSNs, 2010 Proceedings IEEE INFOCOM, 2010.
DOI : 10.1109/INFCOM.2010.5462078

G. [. Wolsey, M. L. Nemhauser, and . Fisher, An analysis of approximations for maximizing submodular set functions, Mathematical Programming, vol.14, pp.265-294, 1978.

M. Girvan and M. E. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, pp.7821-7826, 2002.
DOI : 10.1073/pnas.122653799

A. Gubichev and T. Neumann, Path query processing on very large rdf graphs, WebDB, 2011.

S. Guha, K. Tang, and P. Francis, NOYB, Proceedings of the first workshop on Online social networks, WOSP '08, 2008.
DOI : 10.1145/1397735.1397747

G. Hay, D. Miklau, D. Jensen, P. Towsley, and . Weis, Resisting structural re-identification in anonymized social networks, Proc. VLDB Endow, pp.102-114, 2008.

]. D. Hoc97a and . Hochbaum, Approximation algorithms for np-hard problems, 1997.

D. S. Hochbaum, Approximation algorithms for np-hard problems. chapter Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems, pp.94-143, 1997.

S. Jahid, P. Mittal, and N. Borisov, EASiER, Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, ASIACCS '11, pp.411-415, 2011.
DOI : 10.1145/1966913.1966970

S. Jahid, S. Nilizadeh, P. Mittal, N. Borisov, and A. Kapadia, DECENT: A decentralized architecture for enforcing privacy in online social networks, 2012 IEEE International Conference on Pervasive Computing and Communications Workshops, pp.326-332, 2012.
DOI : 10.1109/PerComW.2012.6197504

D. S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.38-49, 1973.
DOI : 10.1145/800125.804034

R. Jin, N. Ruan, S. Dey, and J. Y. Xu, SCARAB, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, pp.169-180, 2012.
DOI : 10.1145/2213836.2213856

[. Jin, N. Ruan, Y. Xiang, and V. Lee, A highway-centric labeling approach for answering distance queries on large sparse graphs, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, pp.445-456, 2012.
DOI : 10.1145/2213836.2213887

[. Jin, N. Ruan, Y. Xiang, and H. Wang, Path-tree, ACM Transactions on Database Systems, vol.36, issue.1, pp.1-7, 2011.
DOI : 10.1145/1929934.1929941

[. Jin, Y. Xiang, N. Ruan, and D. Fuhry, 3-HOP, Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD '09, pp.813-826, 2009.
DOI : 10.1145/1559845.1559930

J. M. Kleinberg, R. Kumar, P. Raghavan, A. S. Sridhar-rajagopalan, and . Tomkins, The Web as a Graph: Measurements, Models, and Methods, COCOON, pp.1-17, 1999.
DOI : 10.1007/3-540-48686-0_1

M. Kasneci, M. Ramanath, F. M. Sozio, G. Suchanek, and . Weikum, STAR: Steiner-Tree Approximation in Relationship Graphs, 2009 IEEE 25th International Conference on Data Engineering, pp.868-879, 2009.
DOI : 10.1109/ICDE.2009.64

M. Lucas and N. Borisov, Flybynight: mitigating the privacy risks of social networking. SOUPS, 2009.

]. B. Lhl-+-12, T. Li, L. Huang, Y. Liu, K. Cai et al., Identification of colorectal cancer related genes with mrmr and shortest path in protein-protein interaction network, PLoS One, vol.7, issue.4, p.33393, 2012.

J. Leskovec, J. Kleinberg, and C. Faloutsos, Graphs over time, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining , KDD '05, pp.177-187, 2005.
DOI : 10.1145/1081870.1081893

E. Leskovec, J. Kleinberg, and C. Faloutsos, Graph evolution, ACM Transactions on Knowledge Discovery from Data, vol.1, issue.1, 2007.
DOI : 10.1145/1217299.1217301

J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web , WWW '08, pp.695-704, 2008.
DOI : 10.1145/1367497.1367591

E. Liu, H. W. Lim, M. Lauw, A. Le, J. Sun et al., Predicting trusts among users of online communities, Proceedings of the 9th ACM conference on Electronic commerce, EC '08, 2008.
DOI : 10.1145/1386790.1386838

S. Maslov and K. Sneppen, Specificity and Stability in Topology of Protein Networks, Science, vol.296, issue.5569, pp.910-913, 2002.
DOI : 10.1126/science.1065103

M. E. Newman, The Structure and Function of Complex Networks, SIAM Review, vol.45, issue.2, pp.167-256, 2003.
DOI : 10.1137/S003614450342480

S. Njm-+-12-]-shirin-nilizadeh, P. Jahid, N. Mittal, A. Borisov, and . Kapadia, Cachet: a decentralized architecture for privacy preserving social networking with caching, CoNEXT, pp.337-348, 2012.

S. Seufert, A. Anand, S. Bedathur, and G. Weikum, FERRARI: Flexible and efficient reachability range assignment for graph indexing, 2013 IEEE 29th International Conference on Data Engineering (ICDE), 2013.
DOI : 10.1109/ICDE.2013.6544893

M. Shehab, G. Cheek, H. Touati, A. C. Squicciarini, and P. Cheng, Learning based access control in online social networks, Proceedings of the 19th international conference on World wide web, WWW '10, 2010.
DOI : 10.1145/1772690.1772863

A. Cinzia-squicciarini, M. Shehab, and F. Paci, Collective privacy management in social networks, Proceedings of the 18th international conference on World wide web, WWW '09, 2009.
DOI : 10.1145/1526709.1526780

R. Schenkel, A. Theobald, and G. Weikum, HOPI: An Efficient Connection Index for Complex XML Document Collections, EDBT, 2004.
DOI : 10.1007/978-3-540-24741-8_15

M. Schwartz and D. C. Wood, Discovering shared interests using graph analysis, Communications of the ACM, vol.36, issue.8, pp.78-89, 1992.
DOI : 10.1145/163381.163402

A. Sahai and B. Waters, Fuzzy Identity-Based Encryption, EUROCRYPT, pp.457-473, 2005.
DOI : 10.1007/11426639_27

J. Travers, S. Milgram, J. Travers, and S. Milgram, An Experimental Study of the Small World Problem, Sociometry, vol.32, issue.4, pp.425-443, 1969.
DOI : 10.2307/2786545

C. Vicknair, M. Macias, Z. Zhao, X. Nan, Y. Chen et al., A comparison of a graph database and a relational database, Proceedings of the 48th Annual Southeast Regional Conference on, ACM SE '10, pp.421-463, 2010.
DOI : 10.1145/1900008.1900067

J. Sebastiaan, . Van-schaik, and . Oege-de-moor, A memory efficient reachability data structure through bit vector compression. SIGMOD, pp.913-924, 2011.

J. Wang and J. Cheng, Truss decomposition in massive networks, Proc. VLDB Endow, pp.812-823, 2012.
DOI : 10.14778/2311906.2311909

F. Wei, TEDI, Proceedings of the 2010 international conference on Management of data, SIGMOD '10, pp.99-110, 2010.
DOI : 10.1145/1807167.1807181

E. B. Wilson, Probable Inference, the Law of Succession, and Statistical Inference, Journal of the American Statistical Association, vol.22, issue.158, pp.209-212, 1927.
DOI : 10.1080/01621459.1927.10502953

J. Wortham, More employers use social networks to check out applicants . The New York Times, 2009.

J. Hu and Z. Chen, isac: Intimacy based access control for social network sites, Proceedings of the 2012 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing, pp.517-524, 2012.

Q. Xiao, H. Htet-aung, and K. Tan, Towards ad-hoc circles in social networking sites, Proceedings of the 2nd ACM SIGMOD Workshop on Databases and Social Networks, DBSocial '12, pp.19-24, 2012.
DOI : 10.1145/2304536.2304540

W. Wu, J. Pei, W. Wang, and Z. He, Efficiently indexing shortest paths by exploiting symmetry in graphs, pp.493-504, 2009.

H. Yildirim, V. Chaoji, and M. J. Zaki, GRAIL, Proc. VLDB Endow, 2010.
DOI : 10.14778/1920841.1920879

B. Zhou, J. Pei, and W. Luk, A brief survey on anonymization techniques for privacy preserving publishing of social network data, ACM SIGKDD Explorations Newsletter, vol.10, issue.2, pp.12-22, 2008.
DOI : 10.1145/1540276.1540279