×

Sitting closer to friends than enemies, revisited. (English) Zbl 1312.05067

Summary: Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, A.-M. Kermarrec and C. Thraves [Lect. Notes Comput. Sci. 6907, 388–399 (2011; Zbl 1343.68184)] initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space \(\mathbb {R}^{l}\) in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into \(\mathbb {R}^{1}\) can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this case, answering several questions posed by Kermarrec and Thraves [loc. cit.]. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the exponential time hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

MSC:

05C22 Signed and weighted graphs
05C62 Graph representations (geometric and intersection representations, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91D30 Social networks; opinion dynamics

Citations:

Zbl 1343.68184
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Antal, T., Krapivsky, P.L., Redner, S.: Dynamics of social balance on networks. Phys. Rev. E 72(3), 036121 (2005) · Zbl 1130.91041 · doi:10.1103/PhysRevE.72.036121
[2] Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. In: Kolman, P., Kratochvíl, J. (eds.), WG, volume 6986 of Lecture Notes in Computer Science, pp. 47-58. Springer (2011) · Zbl 1341.05218
[3] Cartwright, D., Harary, F.: Structural balance: a generalization of heider’s theory. Psychol Rev 63(5), 277-293 (1956) · doi:10.1037/h0046049
[4] Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55(2), 99-104 (1995) · Zbl 0875.68690 · doi:10.1016/0020-0190(95)00046-F
[5] Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Sitting closer to friends than enemies, revisited. In: Rovan, B., Sassone, V., Widmayer, P. (eds.), MFCS, volume 7464 of Lecture Notes in Computer Science, pp. 296-307. Springer (2012) · Zbl 1365.68351
[6] Davis, J.A.: Clustering and structural balance in graphs. Hum. Relat. 20(2), 181 (1967) · doi:10.1177/001872676702000206
[7] Eppstein, D., Mumford, E.: Self-overlapping curves revisited. In: Mathieu, C. (ed.), SODA, pp. 160-169. SIAM (2009) · Zbl 1421.68172
[8] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979) · Zbl 0411.68039
[9] Guillemot, S., Jansson, J., Sung, W.-K.: Computing a smallest multilabeled phylogenetic tree from rooted triplets. IEEE/ACM Trans. Comput. Biol. Bioinform. 8(4), 1141-1147 (2011) · doi:10.1109/TCBB.2010.77
[10] Ibarra, L.: A simple algorithm to find hamiltonian cycles in proper interval graphs. Inf. Process. Lett. 109(18), 1105-1108 (2009) · Zbl 1197.05085 · doi:10.1016/j.ipl.2009.07.010
[11] Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62 (2), 367-375 (2001) · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727
[12] Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512-530 (2001) · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774
[13] Ioannidou, K., Mertzios, G.B., Nikolopoulos, S.D.: The longest path problem is polynomial on interval graphs. In: Královic, R., Niwinski, D. (eds.), MFCS, volume 5734 of Lecture Notes in Computer Science, pp. 403-414. Springer (2009) · Zbl 1250.68128
[14] Kermarrec, A.-M., Thraves, C.: Can everybody sit closer to their friends than their enemies? In: Murlak, F., Sankowski, P. (eds.) MFCS, volume 6907 of Lecture Notes in Computer Science, pp. 388-399. Springer (2011) · Zbl 1343.68184
[15] Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., Luca, E.W. De, Albayrak, S.: Spectral analysis of signed graphs for clustering, prediction and visualization. In: SDM, p. 559. SIAM (2010) · Zbl 0794.68115
[16] Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Governance in social media: A case study of the wikipedia promotion process. In: Cohen, W.W., Gosling, S. (eds.) ICWSM. The AAAI Press (2010) · Zbl 1197.05085
[17] Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Predicting positive and negative links in online social networks. In: Rappa, M., Jones, P., Freire, J., Chakrabarti, S. (eds.), WWW, pp. 641-650. ACM (2010)
[18] Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Signed networks in social media. In: Mynatt, E.D., Schoner, D., Fitzpatrick, G., Hudson, S.E., Edwards, W.K., Rodden, T. (eds.), CHI, pp. 1361-1370. ACM (2010)
[19] Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15-25 (1993) · Zbl 0794.68115 · doi:10.1016/0898-1221(93)90308-I
[20] George, B.: Mertzios. A polynomial algorithm for the k-cluster problem on the interval graphs. Electron. Notes Discret. Math. 26, 111-118 (2006) · Zbl 1225.05184 · doi:10.1016/j.endm.2006.08.020
[21] Szell, M., Lambiotte, R., Thurner, S.: Multirelational organization of large-scale social networks in an online world. PNAS 107 (31), 13636-13641 (2010) · doi:10.1073/pnas.1004008107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.