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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Distance-Based Clique Relaxations in Networks: s-Clique and s-Club

verfasst von : Shahram Shahinpour, Sergiy Butenko

Erschienen in: Models, Algorithms, and Technologies for Network Analysis

Verlag: Springer New York

Einloggen

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

search-config
loading …

Abstract

The concept of the clique, originally introduced as a model of a cohesive subgroup in the context of social network analysis, is a classical model of a cluster in networks. However, the ideal cohesiveness properties guaranteed by the clique definition put limitations on its applicability to situations where enforcing such properties is unnecessary or even prohibitive. Motivated by practical applications of diverse origins, numerous clique relaxation models, which are obtained by relaxing certain properties of a clique, have been introduced and studied by researchers representing different fields. Distance-based clique relaxations, which replace the requirement on pairwise distances to be equal to 1 in a clique with less restrictive distance bounds, are among the most important such models. This chapter surveys the up-to-date progress made in studying two common distance-based clique relaxation models called s-clique and s-club, as well as the corresponding optimization problems.

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 Kernel Principal Component Analysis: Applications, Implementation and Comparison
Nächstes Kapitel GRASP with Path-Relinking for Facility Layout
Literatur
1.
Abello, J., Resende, M.G.C., Sudarsky, S.: Massive quasi-clique detection. In: Rajsbaum, S. (ed.) LATIN 2002: Theoretical Informatics, pp. 598–612. Springer, London (2002) CrossRef
2.
Adler, N.: Competition in a deregulated air transportation market. Eur. J. Oper. Res. 129, 337–345 (2001) CrossRefMATH
3.
4.
5.
Arora, S., Lund, C., Motwani, R., Szegedy, M.: Proof verification and hardness of approximation problems. J. ACM 45, 501–555 (1998) MathSciNetCrossRefMATH
6.
7.
Asahiro, Y., Miyano, E., Samizo, K.: Approximating maximum diameter-bounded subgraphs. In: Proceedings of the 9th Latin American Conference on Theoretical Informatics (LATIN’10), pp. 615–626. Springer, Berlin (2010) CrossRef
8.
Bader, J.S., Chaudhuri, A., Rothberg, J.M., Chant, J.: Gaining confidence in high-throughput protein interaction networks. Nat. Biotechnol. 22, 78–85 (2004) CrossRef
9.
Balasundaram, B., Butenko, S.: Graph domination, coloring and cliques in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 865–890. Springer, New York (2006) CrossRef
10.
Balasundaram, B., Butenko, S., Trukhanov, S.: Novel approaches for analyzing biological networks. J. Comb. Optim. 10, 23–39 (2005) MathSciNetCrossRefMATH
11.
12.
13.
Bollobás, B.: Extremal Graph Theory. Academic Press, New York (1978) MATH
14.
Bollobás, B.: Random Graphs. Academic Press, New York (1985) MATH
15.
Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 1–74. Kluwer Academic, Dordrecht (1999) CrossRef
16.
Bourjolly, J.-M., Laporte, G., Pesant, G.: Heuristics for finding k-clubs in an undirected graph. Comput. Oper. Res. 27, 559–569 (2000) MathSciNetCrossRefMATH
17.
Bourjolly, J.-M., Laporte, G., Pesant, G.: An exact algorithm for the maximum k-club problem in an undirected graph. Eur. J. Oper. Res. 138, 21–28 (2002) MathSciNetCrossRefMATH
18.
Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979) CrossRefMATH
19.
Buchanan, A., Sung, J.S., Butenko, S., Boginski, V., Pasiliao, E.: On connected dominating sets of restricted diameter. Working paper (2012)
20.
Butenko, S., Wilhelm, W.: Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173, 1–17 (2006) MathSciNetCrossRefMATH
21.
Carraghan, R., Pardalos, P.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375–382 (1990) CrossRefMATH
22.
Carvalho, F.D., Almeida, M.T.: Upper bounds and heuristics for the 2-club problem. Eur. J. Oper. Res. 210(3), 489–494 (2011) MathSciNetCrossRefMATH
23.
Chang, M.S., Hung, L.J., Lin, C.R., Su, P.C.: Finding large k-clubs in undirected graphs. In: Proc. 28th Workshop on Combinatorial Mathematics and Computation Theory (2011)
24.
Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72, 1346–1367 (2006) MathSciNetCrossRefMATH
25.
26.
Dekker, A., Pérez-Rosés, H., Pineda-Villavicencio, G., Watters, P.: The maximum degree & diameter-bounded subgraph and its applications. J. Math. Model. Algorithms 11, 249–268 (2012) MathSciNetCrossRefMATH
27.
Dekker, A.H.: Social network analysis in military headquarters using CAVALIER. In: Proceedings of Fifth International Command and Control Research and Technology Symposium, Canberra, Australia, pp. 24–26 (2000)
28.
29.
30.
31.
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999) CrossRef
32.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979) MATH
33.
Gendreau, M., Soriano, P., Salvail, L.: Solving the maximum clique problem using a tabu search approach. Ann. Oper. Res. 41, 385–403 (1993) CrossRefMATH
34.
35.
36.
Hartung, S., Komusiewicz, C., Nichterlein, A.: Parameterized algorithmics and computational experiments for finding 2-clubs. In: Thilikos, D., Woeginger, G. (eds.) Parameterized and Exact Computation. Lecture Notes in Computer Science, vol. 7535, pp. 231–241. Springer, Berlin (2012) CrossRef
37.
Hartung, S., Komusiewicz, C., Nichterlein, A.: On structural parameterizations for the 2-club problem. In: Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM ’13). Lecture Notes in Computer Science, vol. 7741, pp. 233–243. Springer, Berlin (2013)
38.
Jaillet, P., Song, G., Yu, G.: Airline network design and hub location problems. Location Sci. 4, 195–212 (1996) CrossRefMATH
39.
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972) CrossRef
40.
Kim, D., Wu, Y., Li, Y., Zou, F., Du, D.-Z.: Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Trans. Parallel Distrib. Syst. 20(2), 147–157 (2009) CrossRef
41.
Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15, 169–190 (1950) MathSciNetCrossRef
42.
43.
Mahdavi Pajouh, F.: Polyhedral combinatorics, complexity & algorithms for k-clubs in graphs. PhD thesis, Oklahoma State University (July 2012)
44.
Mahdavi Pajouh, F., Balasundaram, B.: On inclusionwise maximal and maximum cardinality k-clubs in graphs. Discrete Optim. 9(2), 84–97 (2012) MathSciNetCrossRefMATH
45.
46.
Memon, N., Kristoffersen, K.C., Hicks, D.L., Larsen, H.L.: Detecting critical regions in covert networks: a case study of 9/11 terrorists network. In: The Second International Conference on Availability, Reliability and Security, pp. 861–870 (2007) CrossRef
47.
Miao, J., Berleant, D.: From paragraph networks to document networks. In: Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC 2004), vol. 1, pp. 295–302 (2004)
48.
49.
Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13, 161–173 (1979) CrossRef
50.
51.
52.
Pasupuleti, S.: Detection of protein complexes in protein interaction networks using n-clubs. In: Proceedings of the 6th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Lecture Notes in Computer Science, vol. 4973, pp. 153–164. Springer, Berlin (2008) CrossRef
53.
Pattillo, J., Wang, Y., Butenko, S.: On distance-based clique relaxations in unit disk graphs. Working paper (2012)
54.
55.
Rothenberg, R.B., Potterat, J.J., Woodhouse, D.E.: Personal risk taking and the spread of disease: beyond core groups. J. Infect. Dis. 174(Supp. 2), S144–S149 (1996) CrossRef
56.
Sageman, M.: Understanding Terrorist Networks. University of Pennsylvania Press, Philadelphia (2004)
57.
Sampson, R.J., Groves, B.W.: Community structure and crime: testing social-disorganization theory. Am. J. Sociol. 94, 774–802 (1989) CrossRef
58.
Schäfer, A.: Exact algorithms for s-club finding and related problems. Master’s thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena (2009)
59.
Schäfer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6, 883–891 (2012) MathSciNetCrossRefMATH
60.
Scott, J.: Social Network Analysis: A Handbook, 2nd edn. Sage, London (2000)
61.
62.
63.
64.
Terveen, L., Hill, W., Amento, B.: Constructing, organizing, and visualizing collections of topically related web resources. ACM Trans. Comput.-Hum. Interact. 6, 67–94 (1999) CrossRef
65.
Veremyev, A., Boginski, V.: Identifying large robust network clusters via new compact formulations of maximum k-club problems. Eur. J. Oper. Res. 218(2), 316–326 (2012) MathSciNetCrossRefMATH
66.
Wasserman, S., Faust, K.: Social Network Analysis. Cambridge University Press, New York (1994)
67.
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103–128 (2007) MathSciNetCrossRef
Metadaten
Titel
Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
verfasst von
Shahram Shahinpour
Sergiy Butenko
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Models, Algorithms, and Technologies for Network Analysis

Print ISBN: 978-1-4614-8587-2

Electronic ISBN: 978-1-4614-8588-9

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-8588-9_10

Premium Partner

    Bildnachweise