| Revue: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000368974 |
| ISSN: | 1405-5546 |
| Autores: | Alonso, Roberto1 Monroy, Raúl1 |
| Instituciones: | 1Instituto Tecnológico y de Estudios Superiores de Monterrey, Departamento de Ciencias de la Computación, Atizapán, Estado de México. México |
| Año: | 2013 |
| Periodo: | Oct-Dic |
| Volumen: | 17 |
| Número: | 4 |
| Paginación: | 489-500 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Aplicado, descriptivo |
| Resumen en español | En este trabajo demostramos que el problema que llamamos Comunalidad de grupos sociales (SGC por sus siglas en inglés) es NP-completo. Este problema consulta la comunalidad entre los objetos tocados por una colección de agentes que ejecutan acciones. Aunque se presenta naturalmente en varios contextos e.g., perfilar el comportamiento de un conjunto de usuarios de un sistema, SGC ha sido, acorde al conocimiento de los autores, ignorado. Nuestra demostración consiste en una reducción de Karp a partir del problema conocido como Longest Common Subsequence (LCS). Probamos también que un caso especial, al que llamamos 2-SGC, donde la comunalidad entre las acciones esta limitada a pares de agentes, sigue siendo NP-completo. Para probar 2-SGC, nuestra reducción parte del problema conocido como Hitting Set. Antes de concluir con el articulo, especulamos que la versión de optimización de SGC es NP-duro, dando indicaciones de como realizar la demostración necesaria |
| Resumen en inglés | We prove the NP-completeness of the so-called Social Group Commonality (SGC) problem which queries the commonality among the objects 'touched' by collections of agents while executing an action. Although it naturally arises in several contexts, e.g., in profiling the behavior of a collection of system users, SGC (to the authors' knowledge) has been ignored. Our proof of SGC NP-completeness consists of a Karp reduction from the well-known Longest Common Subsequence (LCS) problem to SGC. We also prove that a special case of SGC which we call 2-SGC, where the commonality among actions is limited to agent pairs, remains NP-complete. For proving NP-completeness of 2-SGC though, our reduction departs from the well-known Hitting Set problem. Finally, we hypothesize that the optimality version of SGC is NP-hard, hinting on how to deal with the proof obligation |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Procesamiento de datos, Usuarios, Teoría de la complejidad, Redes sociales, Comunalidad de grupos sociales |
| Keyword: | Computer science, Data processing, Users, Complexity theory, Social networks, Social groups commonality |
| Texte intégral: | Texto completo (Ver HTML) |
