nach oben

Computing

Erschienen in:

16.02.2022 | Regular Paper

Network structure optimization for social networks by minimizing the average path length

verfasst von: Wei Du, Gang Li, Xiaochen He

Erschienen in: Computing | Ausgabe 6/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Network structure plays an important role in the natural and social sciences. Optimization of network structure in achieving specified goals has been a major research focus. In this paper, we focus on structural optimization in terms of minimizing the network’s average path length (APL) by adding edges. We suggest a memetic algorithm to find the minimum-APL solution by adding edges. Experiments show that the proposed algorithm can solve this problem efficiently. Further, we find that APL will ultimately decrease linearly in the process of adding edges, which is affected by the network diameter.

Vorheriger Artikel Scalability and performance analysis of BDPS in clouds

Nächster Artikel Users opinion and emotion understanding in social media regarding COVID-19 vaccine

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

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

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+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

Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826. https://doi.org/10.1073/pnas.122653799MathSciNetCrossRefMATH

Karrer B, Newman MEJ (2011) Stochastic blockmodels and community structure in networks. Phys Rev E Stat Nonlinear Soft Matter Phys 83:016107. https://doi.org/10.1103/PhysRevE.83.016107

Gao C, Ma Z, Zhang AY, Zhou HH (2018) Community detection in degree-corrected block models. Ann Stat 46(5):2153–2185. https://doi.org/10.1214/17-AOS1615MathSciNetCrossRefMATH

Wang J, Zhang J, Liu B, Zhu J, Guo J (2021) Fast network community detection with profile-pseudo likelihood methods. J Am Stat Assoc 1–14. https://doi.org/10.1080/01621459.2021.1996378

Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684):440–442. https://doi.org/10.1038/30918

Barabási A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512. https://doi.org/10.1126/science.286.5439.509MathSciNetCrossRefMATH

Albert R, Barabási A-L (2002) Statistical mechanics of complex networks. Rev Mod Phys 74(1):47–97. https://doi.org/10.1103/revmodphys.74.47MathSciNetCrossRefMATH

Wang W, Liu Q-H, Liang J, Hu Y, Zhou T (2019) Coevolution spreading in complex networks. Phys Rep 820:1–51MathSciNetCrossRef

Li A, Zhou L, Su Q, Cornelius SP, Liu Y-Y, Wang L, Levin SA (2020) Evolution of cooperation on temporal networks. Nat Commun 11(1):2259. https://doi.org/10.1038/s41467-020-16088-wCrossRef

10.

Wang Y, Zeng A, Di Z, Fan Y (2011) Enhancing synchronization in growing networks. EPL 96(5). https://doi.org/10.1209/0295-5075/96/58007

11.

Shi D, Chen G, Thong WWK, Yan X (2013) Searching for optimal network topology with best possible synchronizability. IEEE Circuits Syst Mag 13(1):66–75. https://doi.org/10.1109/mcas.2012.2237145CrossRef

12.

Sun Y, Du H, Gong M, Ma L, Wang S (2014) Fast computing global structural balance in signed networks based on memetic algorithm. Physica A 415:261–272. https://doi.org/10.1016/j.physa.2014.07.071MathSciNetCrossRefMATH

13.

Hwang SW, Kweon SJ, Ventura JA (2020) An alternative fuel refueling station location model considering detour traffic flows on a highway road system. J Adv Transp 2020. https://doi.org/10.1155/2020/9473831

14.

Davoodi M, Ghaffari M (2021) Shortest path problem on uncertain networks: an efficient two phases approach. Comput Indus Eng 157. https://doi.org/10.1016/j.cie.2021.107302

15.

Wang T, Cheng H, Wang X (2020) A link addition method based on uniformity of node degree in interdependent power grids and communication networks. Physica A 560:125112CrossRef

16.

Kułakowski K, Gawroński P, Gronek P (2005) The heider balance: a continuous approach. Int J Mod Phys C 16(05):707–716. https://doi.org/10.1142/s012918310500742xCrossRefMATH

17.

Antal T, Krapivsky PL, Redner S (2005) Dynamics of social balance on networks. Phys Rev E Stat Nonlinear Soft Matter Phys 72(3 Pt 2):036121. https://doi.org/10.1103/PhysRevE.72.036121MathSciNetCrossRef

18.

Facchetti G, Iacono G, Altafini C (2011) Computing global structural balance in large-scale signed social networks. Proc Natl Acad Sci USA 108(52):20953–8. https://doi.org/10.1073/pnas.1109521108CrossRef

19.

Yan X, Li C, Zhang L, Hu Y (2016) A new method optimizing the subgraph centrality of large networks. Physica A 444:373–387MathSciNetCrossRef

20.

Barahona F (1982) On the computational complexity of ising spin glass models. J Phys A Math Gen 15(10):3241–3253. https://doi.org/10.1088/0305-4470/15/10/028MathSciNetCrossRef

21.

Wang S, Gong M, Du H, Ma L, Miao Q, Du W (2016) Optimizing dynamical changes of structural balance in signed network based on memetic algorithm. Social Netw 44:64–73. https://doi.org/10.1016/j.socnet.2015.06.004CrossRef

22.

Yang X, Xiaohua W (2007) Decentralized small-world optimization strategy. J Suzhou Univ 27(3):41–46. https://doi.org/10.3969/j.issn.1673-047X.2007.03.010CrossRef

23.

Schleich J, Danoy G, Dorronsoro B, Bouvry P (2014) Optimising small-world properties in vanets: centralised and distributed overlay approaches. Appl Soft Comput 21:637–646. https://doi.org/10.1016/j.asoc.2014.03.045CrossRef

24.

Du H, Fan J, He X, Feldman MW (2018) A genetic simulated annealing algorithm to optimize the small-world network generating process. Complexity 2018:1–12. https://doi.org/10.1155/2018/1453898CrossRef

25.

Alstott J, Klymko C, Pyzza PB, Radcliffe M (2019) Local rewiring algorithms to increase clustering and grow a small world. J Compl Netw 7(4):564–584. https://doi.org/10.1093/comnet/cny032MathSciNetCrossRefMATH

26.

Yu F, Li Y, Wu T-J (2010) A temporal ant colony optimization approach to the shortest path problem in dynamic scale-free networks. Physica A 389(3):629–636. https://doi.org/10.1016/j.physa.2009.10.005CrossRef

27.

Ma H, Zeng AP (2003) Reconstruction of metabolic networks from genome data and analysis of their global structure for various organisms. Bioinformatics 19(2):270–277. https://doi.org/10.1093/bioinformatics/19.2.270CrossRef

28.

Wang B, Tang H, Guo C, Xiu Z, Zhou T (2006) Optimization of network structure to random failures. Physica A 368(2):607–614. https://doi.org/10.1016/j.physa.2005.12.050CrossRef

29.

Ashton DJ, Jarrett TC, Johnson NF (2005) Effect of congestion costs on shortest paths through complex networks. Phys Rev Lett 94(5):058701. https://doi.org/10.1103/PhysRevLett.94.058701CrossRef

30.

Lago-Fernández LF, Huerta R, Corbacho F, Sigüenza JA (2000) Fast response and temporal coherent oscillations in small-world networks. Phys Rev Lett 84(12):2758–2761. https://doi.org/10.1103/physrevlett.84.2758CrossRef

31.

Gade PM, Hu C-K (2000) Synchronous chaos in coupled map lattices with small-world interactions. Phys Rev E 62(5):6409–6413. https://doi.org/10.1103/physreve.62.6409CrossRef

32.

Jost J, Joy MP (2001) Spectral properties and synchronization in coupled map lattices. Phys Rev E 65(1). https://doi.org/10.1103/physreve.65.016201

33.

Hong H, Choi MY, Kim BJ (2002) Synchronization on small-world networks. Phys Rev E Stat Nonlinear Soft Matter Phys 65(2 Pt 2):026139. https://doi.org/10.1103/PhysRevE.65.026139CrossRef

34.

Barahona M, Pecora LM (2002) Synchronization in small-world systems. Phys Rev Lett 89(5). https://doi.org/10.1103/PhysRevLett.89.054101

35.

Donetti L, Hurtado PI, Munoz MA (2005) Entangled networks, synchronization, and optimal network topology. Phys Rev Lett 95(18):188701. https://doi.org/10.1103/PhysRevLett.95.188701CrossRef

36.

Xuan Q, Li Y, Wu T-J (2009) Optimal symmetric networks in terms of minimizing average shortest path length and their sub-optimal growth model. Physica A 388(7):1257–1267. https://doi.org/10.1016/j.physa.2008.12.020CrossRef

37.

Keren O (2008) Reduction of average path length in binary decision diagrams by spectral methods. IEEE Trans Comput 57(4):520–531. https://doi.org/10.1109/tc.2007.70811MathSciNetCrossRefMATH

38.

Garijo D, Márquez A, Rodríguez N, Silveira RI (2019) Computing optimal shortcuts for networks. Eur J Oper Res 279(1):26–37. https://doi.org/10.1016/j.ejor.2019.05.018MathSciNetCrossRefMATH

39.

Adamic LA, Adar E (2003) Friends and neighbors on the web. Social Netw 25(3):211–230. https://doi.org/10.1016/s0378-8733(03)00009-1CrossRef

40.

Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Am Soc Inform Sci Technol 58(7):1019–1031. https://doi.org/10.1002/asi.20591CrossRef

41.

Meyerson A, Tagiku B (2009) Minimizing average shortest path distances via shortcut edge addition. Springer, pp 272–285. https://doi.org/10.1007/978-3-642-03685-9_21

42.

Parotsidis N, Pitoura E, Tsaparas P (2015) Selecting shortcuts for a smaller world. In: Proceedings of society for industrial and applied mathematics, pp 28–36. https://doi.org/10.1137/1.9781611974010.4

43.

Papagelis M, Bonchi F, Gionis A (2011) Suggesting ghost edges for a smaller world. Assoc Comput Mach. https://doi.org/10.1145/2063576.2063952

44.

Lazaridou K, Semertzidis K, Pitoura E, Tsaparas P (2015) Identifying converging pairs of nodes on a budget

45.

Lee SH, Holme P (2013) A greedy-navigator approach to navigable city plans. Eur Phys J Special Topics 215(1):135–144. https://doi.org/10.1140/epjst/e2013-01720-8CrossRef

46.

Papagelis M (2015) Refining social graph connectivity via shortcut edge addition. ACM Trans Knowl Discov Data 10(2):1–35. https://doi.org/10.1145/2757281CrossRef

47.

Gozzard A, Ward M, Datta A (2018) Converting a network into a small-world network: Fast algorithms for minimizing average path length through link addition. Inf Sci 422:282–289MathSciNetCrossRef

48.

Papagelis M (2015) Refining social graph connectivity via shortcut edge addition. ACM Trans Knowl Discov Data 10(2). https://doi.org/10.1145/2757281

49.

Brusco M, Steinley D (2011) A tabu-search heuristic for deterministic two-mode blockmodeling of binary network matrices. Psychometrika 76(4):612–33. https://doi.org/10.1007/s11336-011-9221-9MathSciNetCrossRefMATH

50.

Ross BJ, Zuviria E (2006) Evolving dynamic bayesian networks with multi-objective genetic algorithms. Appl Intell 26(1):13–23. https://doi.org/10.1007/s10489-006-0002-6CrossRef

51.

Norman MG, Moscato P et al (1991) A competitive and cooperative approach to complex combinatorial search. In: Proceedings of the 20th informatics and operations research meeting. Citeseer, pp 3–15

52.

Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: a literature review. Swarm Evol Comput 2:1–14. https://doi.org/10.1016/j.swevo.2011.11.003CrossRef

53.

Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts-towards memetic algorithms. Caltech Concurrent Computation Program

54.

Du H, He X, Du W, Feldman MW (2017) Optimization of the critical diameter and average path length of social networks. Complexity 2017:1–11. https://doi.org/10.1155/2017/3203615MathSciNetCrossRefMATH

55.

Du H, Wang J, He X, Du W (2019) A memetic algorithm to optimize critical diameter. Swarm Evol Comput 47:56–65. https://doi.org/10.1016/j.swevo.2017.10.001CrossRef

56.

Niu J, Wang L (2016) Structural properties and generative model of non-giant connected components in social networks. Science China Inform Sci 59(12). https://doi.org/10.1007/s11432-015-0790-x

57.

Newman MEJ (2002) Assortative mixing in networks. Phys Rev Lett 89(20). https://doi.org/10.1103/physrevlett.89.208701

58.

Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: can geographic isolation explain this unique trait? Behav Ecol Sociobiol 54(4):396–405CrossRef

59.

Hayes B (2006) Connecting the dots. can the tools of graph theory and social-network studies unravel the next big plot? Am Sci 94(5):400–404

60.

Sundaresan SR, Fischhoff IR, Dushoff J, Rubenstein DI (2007) Network metrics reveal differences in social organization between two fission-fusion species. Grevy’s zebra and onager. Oecologia 151(1):140–149

Titel: Network structure optimization for social networks by minimizing the average path length
verfasst von: Wei Du
Gang Li
Xiaochen He
Publikationsdatum: 16.02.2022
Verlag: Springer Vienna
Erschienen in: Computing / Ausgabe 6/2022
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-022-01061-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 6/2022

Evaluation of fog application placement algorithms: a survey

Virtual machine migration policy for multi-tier application in cloud computing based on Q-learning algorithm

Solving dimension reduction problems for classification using Promoted Crow Search Algorithm (PCSA)

Trust on wheels: Towards secure and resource efficient IoV networks

An ECC-based lightweight remote user authentication and key management scheme for IoT communication in context of fog computing

Scalability and performance analysis of BDPS in clouds