Skip to main content

Research Repository

Advanced Search

Algorithms for diversity and clustering in social networks through dot product graphs

Johnson, M.; Paulusma, D.; van Leeuwen, E.J.

Algorithms for diversity and clustering in social networks through dot product graphs Thumbnail


Authors

E.J. van Leeuwen



Abstract

In this paper, we investigate a graph-theoretical model of social networks. 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 View the MathML source 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 View the MathML source, for some fixed, positive threshold t. The resulting graph is called a d-dot product graph. We consider diversity and clustering in social networks by using a d-dot product graph model for the network. Diversity is considered through the size of the largest independent set of the graph, and clustering through the size of the largest clique. We present both positive and negative results on the potential of this model. We obtain a tight result for the diversity problem, namely that it is polynomial-time solvable for d = 2, but NP-hard 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 give new insights into the structure of dot product graphs. We also consider the situation when two individuals u and v are connected if and only if their preferences are not antithetical, that is, if and only if View the MathML source, and the situation when two individuals u and v are connected if and only if their preferences are neither antithetical nor “orthogonal”, that is, if and only if View the MathML source. For these two cases we prove that the diversity problem is polynomial-time solvable for any fixed d and that the clustering problem is polynomial-time solvable for d ≤ 3.

Citation

Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001

Journal Article Type Article
Publication Date May 1, 2015
Deposit Date Jan 8, 2015
Publicly Available Date Mar 29, 2024
Journal Social Networks
Print ISSN 0378-8733
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 41
Pages 48-55
DOI https://doi.org/10.1016/j.socnet.2015.01.001
Keywords Social network, d-Dot product graph, Independent set, Clique.

Files

Accepted Journal Article (350 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Social Networks. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Social Networks, 41, May 2015, 10.1016/j.socnet.2015.01.001.





You might also like



Downloadable Citations