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 av 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 au · av ≥ 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adamic, L.A., Adar, E.: Friends and neighbors on the Web. Social Networks 25, 211–230 (2003)
Arora, S., Steurer, D., Wigderson, A.: Towards a Study of Low-Complexity Graphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 119–131. Springer, Heidelberg (2009)
Barabási, A.-L., Albert, R.: Emergence of Scaling in Random Networks. Science 286, 509–512 (1999)
Barvinok, A.: A Course in Convexity. American Mathematical Society (2003)
Breiger, R.L.: The Duality of Persons and Groups. Social Forces 53, 181–190 (1974)
Bhawalkar, K., Kleinberg, J., Lewi, K., Roughgarden, T., Sharma, A.: Preventing Unraveling in Social Networks: The Anchored k-Core Problem. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 440–451. Springer, Heidelberg (2012)
Caldarelli, G., Capocci, A., de Los Rios, P., Muñoz, M.A.: Scale-Free Networks from Varying Vertex Intrinsic Fitness. Phys. Rev. Lett. 89, 258702 (2002)
Diestel, R.: Graph Theory. Springer (2005)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141, 109–131 (1995)
Fiduccia, C.M., Scheinerman, E.R., Trenk, A., Zito, J.S.: Dot product representations of graphs. Discrete Mathematics 181, 113–138 (1998)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comp. Sci. 1, 237–267 (1976)
Gray, L.J., Wilson, D.G.: Nonnegative factorization of positive semidefinite nonnegative matrices. Linear Algebra and its Applications 31, 119–127 (1980)
Håstad, J.: Clique is hard to approximate within n 1 − ε. Acta Mathematica 182, 105–142 (1999)
Hoff, P.D., Raftery, A.E., Handcock, M.S.: Latent Space Approaches to Social Network Analysis. J. Am. Stat. Assoc. 97, 1090–1098 (2002)
Hopcroft, J.E., Karp, R.M.: An n 5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2, 225–231 (1973)
Kang, R.J., Lovász, L., Müller, T., Scheinerman, E.R.: Dot product representations of planar graphs. Electr. J. Comb. 18 (2011)
Kang, R.J., Müller, T.: Sphere and dot product representations of graphs. Discrete and Computational Geometry 47, 548–568 (2012)
Karp, R.M.: Reducibility among Combinatorial Problems, Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
Kim, M., Leskovec, J.: Multiplicative Attribute Graph Model of Real-World Networks. In: Kumar, R., Sivakumar, D. (eds.) WAW 2010. LNCS, vol. 6516, pp. 62–73. Springer, Heidelberg (2010)
Kotlov, A., Lovász, L., Vempala, S.: The Colin de Verdiére number and sphere representations of a graph. Combinatorica 17, 483–521 (1997)
Liben-Nowell, D., Kleinberg, J.: The Link Prediction Problem for Social Networks. In: Proc. CIKM 2003, pp. 556–559 (2003)
McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a Feather: Homophily in Social Networks. Annual Rev. Sociology 27, 415–444 (2001)
Newman, M.E.J.: The Structure and Function of Complex Networks. SIAM Review 45, 167–256 (2003)
Nickel, C.M.L.: Random Dot Product Graphs: A Model for Social Networks. PhD dissertation, Johns Hopkins University (2007)
Papadimitriou, C.H., Raghavan, P., Tamaki, H., Vempala, S.: Latent Semantic Indexing: A Probabilistic Analysis. J. Comput. Syst. Sci. 61, 217–235 (2000)
de, D.J., Price, S.: A general theory of bibliometric and other cumulative advantage processes. J. American Society for Information Science 27, 292–306 (1976)
Reiterman, J., Rödl, V., Šinǎjová, E.: Embeddings of graphs in Euclidean spaces. Discrete and Computational Geometery 4, 349–364 (1989)
Reiterman, J., Rödl, V., Šinǎjová, E.: Geometrical embeddings of graphs. Discrete Mathematics 74, 291–319 (1989)
Reiterman, J., Rödl, V., Šinǎjová, E.: On embedding of graphs into Euclidean spaces of small dimension. J. Combin. Theory B 56, 1–8 (1992)
Scheinerman, E.R., Tucker, K.: Modeling graphs using dot product representations. Computational Statistics 25, 1–16 (2010)
Simon, H.A.: On a class of skew distribution functions. Biom. 42, 425–440 (1955)
Snijders, T.A.B.: Statistical Models for Social Networks. Annual Rev. Sociology 37, 131–153 (2011)
Watts, D.J., Dodds, P.S., Newman, M.E.J.: Identity and Search in Social Networks. Science 296, 1302–1305 (2002)
Young, S.J., Scheinerman, E.R.: Random dot product graph models for social networks. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 138–149. Springer, Heidelberg (2007)
Young, S.J., Scheinerman, E.R.: Directed random dot product graphs. Internet Mathematics 5, 91–111 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnson, M., Paulusma, D., van Leeuwen, E.J. (2013). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)