Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Web Scanner Detection Based on Behavioral Differences Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Greedily Remove k Links to Hide Important Individuals in Social Network

verfasst von : Jie Ji, Guohua Wu, Chenjian Duan, Yizhi Ren, Zhen Wang

Erschienen in: Security and Privacy in Social Networks and Big Data

Verlag: Springer Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Closeness centrality is a type of measure that usually used in social network analysis (SNA). For personal privacy, we study how to help important individuals avoid being detected by closeness centrality analysis. In this paper, we present an optimization problem of finding k edges removed to minimize leader node closeness value to hide leader. We consider this problem in the undirected graph and prove its NP-completeness by reduction from the Hamiltonian cycle problem. Hence, we propose a greedy algorithm with a \((1-\frac{1}{e})\) - approximation lower bound and design UpdateCloseness algorithm to reduce time cost by Breadth-First Search algorithm. Experimental results confirm the effectivity of our greedy scheme.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Design and Implementation of Medical Dispute Governance Based on Blockchain
Nächstes Kapitel Blockchain-Based Threshold Electronic Voting System
Literatur
1.
2.
Beauchamp, M.A.: An improved index of centrality. Behav. Sci. 10(2), 161–163 (1965)CrossRef
3.
Bergamini, E., Borassi, M., Crescenzi, P., Marino, A., Meyerhenke, H.: Computing top-k closeness centrality faster in unweighted graphs. In: ALENEX, pp. 68–80. SIAM (2016)
4.
5.
Bisenius, P., Bergamin, E., Angriman, E., Meyerhenke, H.: Computing top-k closeness centrality in fully-dynamic graphs. In: ALENEX, pp. 21–35. SIAM (2018)
6.
Borassi, M., Crescenzi, P., Marino, A.: Fast and simple computation of top-k closeness centralities. arXiv preprint arXiv:​1507.​01490 (2015)
7.
Chan, S.Y., Leung, I.X., Liò, P.: Fast centrality approximation in modular networks. In: CNIKM, pp. 31–38. ACM (2009)
8.
Cohen, E., Delling, D., Pajor, T., Werneck, R.F.: Computing classic closeness centrality, at scale. In: COSN, pp. 37–50. ACM (2014)
9.
Crescenzi, P., Dangelo, G., Severini, L., Velaj, Y.: Greedily improving our own closeness centrality in a network. TKDD 11(1), 9 (2016)CrossRef
10.
ERDdS, P., R&wi, A.: On random graphs i. Publ. Math. Debrecen 6, 290–297 (1959)
11.
Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry, pp. 35–41 (1977)
12.
Gleiser, P.M., Danon, L.: Community structure in jazz. Adv. Complex Syst. 6(04), 565–573 (2003)CrossRef
13.
Kas, M., Carley, K.M., Carley, L.R.: Incremental closeness centrality for dynamically changing social networks. In: ASONAM, pp. 1250–1258. ACM (2013)
14.
Krebs, V.E.: Mapping networks of terrorist cells. Connections 24(3), 43–52 (2002)
15.
Le Merrer, E., Le Scouarnec, N., Trédan, G.: Heuristical top-k: fast estimation of centralities in complex networks. Inf. Process. Lett. 114(8), 432–436 (2014)MathSciNetCrossRef
16.
Marchiori, M., Latora, V.: Harmony in the small-world. Phys. A Stat. Mech. Appl. 285(3–4), 539–546 (2000)CrossRef
17.
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-i. Math. Program. 14(1), 265–294 (1978)MathSciNetCrossRef
18.
19.
Olsen, P.W., Labouseur, A.G., Hwang, J.H.: Efficient top-k closeness centrality search. In: ICDE, pp. 196–207. IEEE (2014)
20.
Ressler, S.: Social network analysis as an approach to combat terrorism: past,present, and future research. Homel. Secur. Aff. 2(2) (2006)
21.
Rochat, Y.: Closeness centrality extended to unconnected graphs: the harmonic centrality index. Technical report (2009)
22.
Rozemberczki, B., Davies, R., Sarkar, R., Sutton, C.: Gemsec: graph embedding with self clustering (2018)
23.
Santos, E.E., Korah, J., Murugappan, V., Subramanian, S.: Efficient anytime anywhere algorithms for closeness centrality in large and dynamic graphs. In: IPDPSW, pp. 1821–1830. IEEE (2016)
24.
Sariyuce, A.E., Kaya, K., Saule, E., Catalyurek, U.V.: Incremental algorithms for network management and analysis based on closeness centrality. arXiv preprint arXiv:​1303.​0422 (2013)
25.
Saxena, A., Gera, R., Iyengar, S.: A faster method to estimate closeness centrality ranking. arXiv preprint arXiv:​1706.​02083 (2017)
26.
Shaw, M.E.: Group structure and the behavior of individuals in small groups. J. Psychol. 38(1), 139–149 (1954)CrossRef
27.
Takhteyev, Y., Gruzd, A., Wellman, B.: Geography of twitter networks. Soc. Netw. 34, 73–81 (2012)CrossRef
28.
Ter Wal, A.L., Boschma, R.A.: Applying social network analysis in economic geography: framing some key analytic issues. Ann. Reg. Sci. 43(3), 739–756 (2009)CrossRef
29.
Tong, H., Prakash, B.A., Eliassi-Rad, T., Faloutsos, M., Faloutsos, C.: Gelling, and melting, large graphs by edge manipulation. In: CIKM, pp. 245–254. ACM (2012)
30.
Ufimtsev, V., Bhowmick, S.: An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks. In: IAAA, pp. 53–56. IEEE Press (2014)
31.
32.
Waniek, M., Michalak, T.P., Wooldridge, M.J., Rahwan, T.: Hiding individuals and communities in a social network. Nat. Hum. Behav. 2(2), 139 (2018)CrossRef
33.
Watts, D.J., Strogatz, S.H.: Collective dynamics of “small-world” networks. Nature 393(6684), 440 (1998)CrossRef
34.
Yen, C.C., Yeh, M.Y., Chen, M.S.: An efficient approach to updating closeness centrality and average path length in dynamic networks. In: ICDM, pp. 867–876. IEEE (2013)
35.
Zhou, B., Pei, J., Luk, W.: A brief survey on anonymization techniques for privacy preserving publishing of social network data. ACM Sigkdd Explor. Newsl. 10(2), 12–22 (2008)CrossRef
Metadaten
Titel
Greedily Remove k Links to Hide Important Individuals in Social Network
verfasst von
Jie Ji
Guohua Wu
Chenjian Duan
Yizhi Ren
Zhen Wang
Copyright-Jahr
2019
Verlag
Springer Singapore
Buch
Security and Privacy in Social Networks and Big Data

Print ISBN: 978-981-15-0757-1

Electronic ISBN: 978-981-15-0758-8

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-981-15-0758-8_17

Premium Partner

    Bildnachweise