M. Johnson
Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
Johnson, M.; Paulusma, D.; van Leeuwen, E.J.
Authors
Contributors
Leizhen Cai
Editor
Siu-Wing Cheng
Editor
Tak-Wah Lam
Editor
Abstract
Social networks are often analyzed through a graph model of the network. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d-dimensional vector a v represents the extent to which individual v has each of a set of d attributes or opinions. Then two individuals u and v are assumed to be friends, that is, they are connected in the graph model, if and only if a u · a v ≥ t, for some fixed, positive threshold t. The resulting graph is called a d-dot product graph.. We consider two measures for diversity and clustering in social networks by using a d-dot product graph model for the network. Diversity is measured through the size of the largest independent set of the graph, and clustering is measured through the size of the largest clique. We obtain a tight result for the diversity problem, namely that it is polynomial-time solvable for d = 2, but NP-complete for d ≥ 3. We show that the clustering problem is polynomial-time solvable for d = 2. To our knowledge, these results are also the first on the computational complexity of combinatorial optimization problems on dot product graphs. We also consider the situation when two individuals are connected if their preferences are not opposite. This leads to a variant of the standard dot product graph model by taking the threshold t to be zero. We prove in this case that the diversity problem is polynomial-time solvable for any fixed d.
Citation
Johnson, M., Paulusma, D., & van Leeuwen, E. (2013). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. In L. Cai, S. Cheng, & T. Lam (Eds.), Algorithms and computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, 16-18 December 2013 ; proceedings (130-140). https://doi.org/10.1007/978-3-642-45030-3_13
Conference Name | 24th International Symposium, ISAAC 2013 |
---|---|
Conference Location | Hong Kong, China, |
Publication Date | Jan 1, 2013 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Jan 15, 2015 |
Volume | 8283 |
Pages | 130-140 |
Series Title | Lecture notes in computer science |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Algorithms and computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, 16-18 December 2013 ; proceedings. |
ISBN | 9783642450297 |
DOI | https://doi.org/10.1007/978-3-642-45030-3_13 |
Public URL | https://durham-repository.worktribe.com/output/1153609 |
Files
Accepted Conference Proceeding
(306 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-45030-3_13
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search