Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2019 | OriginalPaper | Chapter

Graph Profile Realizations and Applications to Social Networks

Authors : Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The social standing of individuals in a social network is typically determined locally according to the individual’s neighborhood or by a comparison between the individual and its neighbors. In this paper, we consider various criteria that measure social status and the extent in which individuals are satisfied with their social status. We study these criteria from the point of view of network realization: given a satisfaction specification, decide whether there exists a network realizing this specification.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Correction to: Weighted Upper Edge Cover: Complexity and Approximability
next chapter Parameterized Computational Geometry via Decomposition Theorems
Footnotes
1
A similar example can be studied where each vertex i has at least \(s_i\) such neighbors.
 
2
One may consider also a non-uniform version of this example, where different vertices desire different percentiles or different thresholds.
 
3
A more relaxed version requires the vertex degree to be roughly equal to the average degree of its neighbors. See the previous section.
 
Literature
1.
2.
3.
Blitzstein, J.K., Diaconis, P.: A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Math. 6(4), 489–522 (2011)MathSciNetCrossRef
4.
5.
Choudum, S.A.: A simple proof of the Erdös-Gallai theorem on graph sequences. Bull. Aust. Math. Soc. 33(1), 67–70 (1991)MathSciNetCrossRef
6.
Cloteaux, B.: Fast sequential creation of random realizations of degree sequences. Internet Math. 12(3), 205–219 (2016)MathSciNetCrossRef
7.
Eom, Y.-H., Jo, H.-H.: Generalized friendship paradox in complex networks: the case of scientific collaboration. Sci. Rep. 4(4603), 1–6 (2014)
8.
Erdös, P., Gallai, T.: Graphs with prescribed degrees of vertices [Hungarian]. Matematikai Lapok 11, 264–274 (1960)MATH
9.
Feld, S.L.: Why your friends have more friends than you do. Am. J. Sociol. 96, 1464–1477 (1991)CrossRef
10.
Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph - I. SIAM J. Appl. Math. 10(3), 496–506 (1962)MathSciNetCrossRef
11.
Havel, V.: A remark on the existence of finite graphs [in Czech]. Casopis Pest. Mat. 80, 477–480 (1955)MATH
12.
13.
Mihail, M., Vishnoi, N.: On generating graphs with prescribed degree sequences for complex network modeling applications. In: 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (2002)
14.
Mossel, E., Ross, N.: Shotgun assembly of labeled graphs. CoRR, abs/1504.07682 (2015)
15.
16.
Sierksma, G., Hoogeveen, H.: Seven criteria for integer sequences being graphic. J. Graph Theory 15(2), 223–231 (1991)MathSciNetCrossRef
17.
Tripathi, A., Tyagi, H.: A simple criterion on degree sequences of graphs. Discret. Appl. Math. 156(18), 3513–3517 (2008)MathSciNetCrossRef
18.
Ulam, S.M.: A Collection of Mathematical Problems. Wiley, Hoboken (1960)MATH
19.
Wang, D.L., Kleitman, D.J.: On the existence of \(n\)-connected graphs with prescribed degrees (\(n>2\)). Networks 3, 225–239 (1973)MathSciNetCrossRef
20.
Metadata
Title
Graph Profile Realizations and Applications to Social Networks
Authors
Amotz Bar-Noy
Keerti Choudhary
David Peleg
Dror Rawitz
Copyright Year
2019
Book
WALCOM: Algorithms and Computation

Print ISBN: 978-3-030-10563-1

Electronic ISBN: 978-3-030-10564-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-10564-8_1

Premium Partner

    Image Credits