Um Sistema de Predição de Relacionamentos em Redes Sociais
Resumo
Predizer novos relacionamentos dentro de um grupo social é uma tarefa complexa, porém extremamente útil para potencializar ou maximizar colaborações por meio da indicação de quais seriam as parcerias mais promissoras. Nas redes sociais acadêmicas, a predição de relacionamentos é tipicamente utilizada para tentar identificar potenciais parceiros no desenvolvimento de um projeto e/ou coautores para a publicação de um artigo. Este artigo apresenta um sistema que combina técnicas de inteligência artificial com o estado da arte das métricas de predição de relacionamentos em redes sociais. O sistema resultante foi testado usando dados reais de pesquisadores em Ciência da Computação e atingiu uma precisão superior a 99,5% na predição de novas coautorias.
Palavras-chave:
predição de relacionamentos, redes sociais, redes acadêmicas
Referências
C. Medeiros, J. Perez-Alcazar, L. Digiampietri, G. Pastorello, A. Santanche, R. Torres, E. Madeira, and E. Bacarin. WOODSS and the Web: Annotating and Reusing Scientific Workflows. ACM SIGMOD Record, 34(3):18–23, 2005.
C. Perez, B. Birregah, and M. Lemercier. The multi-layer imbrication for data leakage prevention from mobile devices. In Trust, Security and Privacy in Computing and Communications (TrustCom), 2012 IEEE 11th International Conference on, pages 813–819, June 2012.
C. R. do Nascimento Santiago. Desenvolvimento de um ambiente de computação voluntária baseado em computação ponto-a-ponto. Master’s thesis, Universidade de Sao Paulo, 2015.
C.-J. Hsieh, M. Tiwari, D. Agarwal, X. L. Huang, and S. Shah. Organizational overlap on social networks and its applications. In Proceedings of the 22Nd International Conference on World Wide Web, WWW ’13, pages 571–582, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee.
D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM ’03, pages 556–559, New York, NY, USA, 2003. ACM.
D. Quercia and L. Capra. Friendsensing: Recommending friends using mobile phones. In Proceedings of the Third ACM Conference on Recommender Systems, RecSys ’09, pages 273–276, New York, NY, USA, 2009. ACM.
E. Zhong, W. Fan, Y. Zhu, and Q. Yang. Modeling the dynamics of composite social networks. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’13, pages 937–945, New York, NY, USA, 2013. ACM.
H. de Sa and R. Prudencio. Supervised link prediction in weighted networks. In Neural Networks (IJCNN), The 2011 International Joint Conference on, pages 2281–2288, July 2011.
H. He, Y. Bai, E. Garcia, and S. Li. Adasyn: Adaptive synthetic sampling approach for imbalanced learning. In Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on, pages 1322–1328, June 2008.
I. Altintas, C. Berkley, E. Jaeger, M. Jones, B. Ludascher, and S. Mock. Kepler: An extensible system for design and execution of scientific workflows. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management, pages 423–424, Washington, DC, USA, 2004.
I. Taylor, M. Shields, I. Wang, and A. Harrison. Visual grid workflow in triana. Journal of Grid Computing, 3(3-4):153–169, 2005.
J. Goecks, A. Nekrutenko, J. Taylor, and T. G. Team. Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences. Genome Biology, 11(8):R86, 2010.
J. Guo and H. Guo. Multi-features link prediction based on matrix. In Computer Design and Applications (ICCDA), 2010 International Conference on, volume 1, pages V1–357–V1–361, June 2010.
J. Kunegis, J. Preusse, and F. Schwagereit. What is the added value of negative links in online social networks? In Proceedings of the 22Nd International Conference on World Wide Web, WWW ’13, pages 727–736, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee.
L. A. Digiampietri, J. C. Araujo, E. H. Ostroski, C. R. N. Santiago, and J. J. Perez-Alcazar. Combinando workflows e semântica para facilitar o reuso de software. Revista de Informática Teórica e Aplicada: RITA, 20:73–89, 2013.
L. A. Digiampietri, J. P. Mena-Chalco, P. O. S. Vaz de Melo, A. P. R. Malheiro, D. N. O. Meira, L. F. Franco, and L. B. Oliveira. Brax-ray: An x-ray of the brazilian computer science graduate programs. PLoS ONE, 9(4):e94541, 04 2014.
L. A. Digiampietri, V. M. Pereira, C. I. Costa, G. J. dos Santos Junior, F. M. Stefanini, and C. R. Santiago. An extensible framework for genomic and metagenomic analysis. In S. Campos, editor, Advances in Bioinformatics and Computational Biology, volume 8826 of Lecture Notes in Computer Science, pages 1–8. Springer International Publishing, 2014.
L. Digiampietri, B. Teodoro, C. Santiago, G. Oliveira, and J. Araújo. Um sistema de informação extensível para o reconhecimento automático de libras. In SBSI 2012 - Trilhas Técnicas (Technical Tracks), may 2012.
L. Digiampietri, C. Santiago, and C. Alves. Predição de coautorias em redes sociais acadêmicas: um estudo exploratório em ciência da computação. In CSBC-BraSNAM 2013, jul 2013.
L. Lu and T. Zhou. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 390(6):1150 – 1170, 2011.
M. A. Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction using supervised learning. In In Proc. of SDM 06 workshop on Link Analysis, Counterterrorism and Security, 2006.
M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici. Link prediction in social networks using computationally efficient topological features. In Privacy, security, risk and trust (passat), 2011 ieee third international conference on and 2011 ieee third international conference on social computing (socialcom), pages 73–80, Oct 2011.
M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software: an update. SIGKDD Explorations, 11(1):10–18, 2009.
M. Hasan and M. Zaki. A survey of link prediction in social networks. In C. C. Aggarwal, editor, Social Network Data Analytics, pages 243–275. Springer US, 2011.
M. Makrehchi. Social link recommendation by learning hidden topics. In Proceedings of the Fifth ACM Conference on Recommender Systems, RecSys ’11, pages 189–196, New York, NY, USA, 2011. ACM.
P. da Silva Soares and R. Bastos Cavalcante Prudencio. Time series based link prediction. In Neural Networks (IJCNN), The 2012 International Joint Conference on, pages 1–7, June 2012.
S. Gao, L. Denoyer, and P. Gallinari. Link prediction via latent factor blockmodel. In Proceedings of the 21st International Conference Companion on World Wide Web, WWW ’12 Companion, pages 507–508, New York, NY, USA, 2012. ACM.
S. P. Callahan, J. Freire, E. Santos, C. E. Scheidegger, C. T. Silva, and H. T. Vo. Managing the evolution of dataflows with VisTrails. In Proceedings of the 22nd International Conference on Data Engineering Workshops, page 71, 2006.
T. Murata and S. Moriyasu. Link prediction based on structural properties of online social networks. New Generation Computing, 26(3):245–257, 2008.
V. Vasuki, N. Natarajan, Z. Lu, and I. S. Dhillon. Affiliation recommendation using auxiliary networks. In Proceedings of the Fourth ACM Conference on Recommender Systems, RecSys ’10, pages 103–110, New York, NY, USA, 2010. ACM.
W. Cukierski, B. Hamner, and B. Yang. Graph-based features for supervised link prediction. In Neural Networks (IJCNN), The 2011 International Joint Conference on, pages 1237–1244, July 2011.
Y. Dhote, N. Mishra, and S. Sharma. Survey and analysis of temporal link prediction in online social networks. In Advances in Computing, Communications and Informatics (ICACCI), 2013 International Conference on, pages 1178–1183, Aug 2013.
Y. Dong, J. Tang, S. Wu, J. Tian, N. Chawla, J. Rao, and H. Cao. Link prediction and recommendation across heterogeneous social networks. In Data Mining (ICDM), 2012 IEEE 12th International Conference on, pages 181–190, Dec 2012.
Y. Dong, Q. Ke, J. Rao, and B. Wu. Predicting missing links via local feature of common neighbors. In Fuzzy Systems and Knowledge Discovery (FSKD), 2011 Eighth International Conference on, volume 2, pages 1038–1042, July 2011.
Y. Tian, Q. He, Q. Zhao, X. Liu, and W.-c. Lee. Boosting social network connectivity with link revival. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, pages 589–598, New York, NY, USA, 2010. ACM.
Z. Lin, X. Yun, and Y. Zhu. Link prediction using benefitranks in weighted networks. In Proceedings of the The 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology - Volume 01, WI-IAT ’12, pages 423–430, Washington, DC, USA, 2012. IEEE Computer Society.
C. Perez, B. Birregah, and M. Lemercier. The multi-layer imbrication for data leakage prevention from mobile devices. In Trust, Security and Privacy in Computing and Communications (TrustCom), 2012 IEEE 11th International Conference on, pages 813–819, June 2012.
C. R. do Nascimento Santiago. Desenvolvimento de um ambiente de computação voluntária baseado em computação ponto-a-ponto. Master’s thesis, Universidade de Sao Paulo, 2015.
C.-J. Hsieh, M. Tiwari, D. Agarwal, X. L. Huang, and S. Shah. Organizational overlap on social networks and its applications. In Proceedings of the 22Nd International Conference on World Wide Web, WWW ’13, pages 571–582, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee.
D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM ’03, pages 556–559, New York, NY, USA, 2003. ACM.
D. Quercia and L. Capra. Friendsensing: Recommending friends using mobile phones. In Proceedings of the Third ACM Conference on Recommender Systems, RecSys ’09, pages 273–276, New York, NY, USA, 2009. ACM.
E. Zhong, W. Fan, Y. Zhu, and Q. Yang. Modeling the dynamics of composite social networks. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’13, pages 937–945, New York, NY, USA, 2013. ACM.
H. de Sa and R. Prudencio. Supervised link prediction in weighted networks. In Neural Networks (IJCNN), The 2011 International Joint Conference on, pages 2281–2288, July 2011.
H. He, Y. Bai, E. Garcia, and S. Li. Adasyn: Adaptive synthetic sampling approach for imbalanced learning. In Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on, pages 1322–1328, June 2008.
I. Altintas, C. Berkley, E. Jaeger, M. Jones, B. Ludascher, and S. Mock. Kepler: An extensible system for design and execution of scientific workflows. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management, pages 423–424, Washington, DC, USA, 2004.
I. Taylor, M. Shields, I. Wang, and A. Harrison. Visual grid workflow in triana. Journal of Grid Computing, 3(3-4):153–169, 2005.
J. Goecks, A. Nekrutenko, J. Taylor, and T. G. Team. Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences. Genome Biology, 11(8):R86, 2010.
J. Guo and H. Guo. Multi-features link prediction based on matrix. In Computer Design and Applications (ICCDA), 2010 International Conference on, volume 1, pages V1–357–V1–361, June 2010.
J. Kunegis, J. Preusse, and F. Schwagereit. What is the added value of negative links in online social networks? In Proceedings of the 22Nd International Conference on World Wide Web, WWW ’13, pages 727–736, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee.
L. A. Digiampietri, J. C. Araujo, E. H. Ostroski, C. R. N. Santiago, and J. J. Perez-Alcazar. Combinando workflows e semântica para facilitar o reuso de software. Revista de Informática Teórica e Aplicada: RITA, 20:73–89, 2013.
L. A. Digiampietri, J. P. Mena-Chalco, P. O. S. Vaz de Melo, A. P. R. Malheiro, D. N. O. Meira, L. F. Franco, and L. B. Oliveira. Brax-ray: An x-ray of the brazilian computer science graduate programs. PLoS ONE, 9(4):e94541, 04 2014.
L. A. Digiampietri, V. M. Pereira, C. I. Costa, G. J. dos Santos Junior, F. M. Stefanini, and C. R. Santiago. An extensible framework for genomic and metagenomic analysis. In S. Campos, editor, Advances in Bioinformatics and Computational Biology, volume 8826 of Lecture Notes in Computer Science, pages 1–8. Springer International Publishing, 2014.
L. Digiampietri, B. Teodoro, C. Santiago, G. Oliveira, and J. Araújo. Um sistema de informação extensível para o reconhecimento automático de libras. In SBSI 2012 - Trilhas Técnicas (Technical Tracks), may 2012.
L. Digiampietri, C. Santiago, and C. Alves. Predição de coautorias em redes sociais acadêmicas: um estudo exploratório em ciência da computação. In CSBC-BraSNAM 2013, jul 2013.
L. Lu and T. Zhou. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 390(6):1150 – 1170, 2011.
M. A. Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction using supervised learning. In In Proc. of SDM 06 workshop on Link Analysis, Counterterrorism and Security, 2006.
M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici. Link prediction in social networks using computationally efficient topological features. In Privacy, security, risk and trust (passat), 2011 ieee third international conference on and 2011 ieee third international conference on social computing (socialcom), pages 73–80, Oct 2011.
M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software: an update. SIGKDD Explorations, 11(1):10–18, 2009.
M. Hasan and M. Zaki. A survey of link prediction in social networks. In C. C. Aggarwal, editor, Social Network Data Analytics, pages 243–275. Springer US, 2011.
M. Makrehchi. Social link recommendation by learning hidden topics. In Proceedings of the Fifth ACM Conference on Recommender Systems, RecSys ’11, pages 189–196, New York, NY, USA, 2011. ACM.
P. da Silva Soares and R. Bastos Cavalcante Prudencio. Time series based link prediction. In Neural Networks (IJCNN), The 2012 International Joint Conference on, pages 1–7, June 2012.
S. Gao, L. Denoyer, and P. Gallinari. Link prediction via latent factor blockmodel. In Proceedings of the 21st International Conference Companion on World Wide Web, WWW ’12 Companion, pages 507–508, New York, NY, USA, 2012. ACM.
S. P. Callahan, J. Freire, E. Santos, C. E. Scheidegger, C. T. Silva, and H. T. Vo. Managing the evolution of dataflows with VisTrails. In Proceedings of the 22nd International Conference on Data Engineering Workshops, page 71, 2006.
T. Murata and S. Moriyasu. Link prediction based on structural properties of online social networks. New Generation Computing, 26(3):245–257, 2008.
V. Vasuki, N. Natarajan, Z. Lu, and I. S. Dhillon. Affiliation recommendation using auxiliary networks. In Proceedings of the Fourth ACM Conference on Recommender Systems, RecSys ’10, pages 103–110, New York, NY, USA, 2010. ACM.
W. Cukierski, B. Hamner, and B. Yang. Graph-based features for supervised link prediction. In Neural Networks (IJCNN), The 2011 International Joint Conference on, pages 1237–1244, July 2011.
Y. Dhote, N. Mishra, and S. Sharma. Survey and analysis of temporal link prediction in online social networks. In Advances in Computing, Communications and Informatics (ICACCI), 2013 International Conference on, pages 1178–1183, Aug 2013.
Y. Dong, J. Tang, S. Wu, J. Tian, N. Chawla, J. Rao, and H. Cao. Link prediction and recommendation across heterogeneous social networks. In Data Mining (ICDM), 2012 IEEE 12th International Conference on, pages 181–190, Dec 2012.
Y. Dong, Q. Ke, J. Rao, and B. Wu. Predicting missing links via local feature of common neighbors. In Fuzzy Systems and Knowledge Discovery (FSKD), 2011 Eighth International Conference on, volume 2, pages 1038–1042, July 2011.
Y. Tian, Q. He, Q. Zhao, X. Liu, and W.-c. Lee. Boosting social network connectivity with link revival. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, pages 589–598, New York, NY, USA, 2010. ACM.
Z. Lin, X. Yun, and Y. Zhu. Link prediction using benefitranks in weighted networks. In Proceedings of the The 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology - Volume 01, WI-IAT ’12, pages 423–430, Washington, DC, USA, 2012. IEEE Computer Society.
Publicado
26/05/2015
Como Citar
DIGIAMPIETRI, Luciano; MARUYAMA, William; SANTIAGO, Caio; LIMA, Jamison.
Um Sistema de Predição de Relacionamentos em Redes Sociais. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (SBSI), 11. , 2015, Goiânia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 139-146.
DOI: https://doi.org/10.5753/sbsi.2015.5810.
