ALL libraries (COBIB.SI union bibliographic/catalogue database)
-
Centrality measures of large networks : doctoral thesisKrnc, Matjaž, 1987-V večini omrežij so nekatera vozlišča ali povezave pomembnejše od drugih. Pomembnost vozlišč v omrežjih lahko izrazimo z merami centralnosti. Podanemu centralnostnemu indeksu lahko določimo indeks ... Freemanove centralizacije, ki meri relativno centralnost vozlišča v primerjavi s centralnostjno vseh ostalih vozlišč v omrežju. V tej disertaciji analiziramo različne strukturne indekse, kot so stopnja točk, ekscentričnost, centralnost bližine, vmesnostna centralnost, Wienerjev indeks ter totalna razdalja. Potrdimo domnevo avtorjev Everett, Sinclair in Dankelmann glede maksimiziranja bližinske centralizacije v dvodelnih omrežjih, s podanimi velikostmi biparticij. Trdimo, da je največja vrednost centralizacije bližine (med vsemi dvodelnimi omrežji) dosežena, če lokalno maksimiziramo bližinsko centralnost v neki točki. Izkaže se, da je ekstremalna konfiguracija dosežena v korenskem drevesu globine ▫$2$▫, z dodatnim pogojem, da imajo vsi sosedje od korena skoraj enako stopnjo. Med drugim določimo maksimizirajočo vrednost ekscentrične centralizacije ter najdemo nekaj maksimizirajočih omrežij za družine dvodelnih grafov s podanimi velikostmi biparticij, dreves fiksne velikosti s podano maksimalno stopnjo, kot tudi splošnih povezanih omrežij pri podanem številu vozlišč ali povezav. Tekom omenjene analize predstavimo tudi nov način enumeracije drevesnih vozlišč. Totalna razdalja vozlišča ▫$v$▫ je enaka vsoti vseh razdalj med ▫$v$▫ ter vsemi drugimi vozlišči v omrežju. Pri analizi centralizacije totalne razdalje določimo grafe na ▫$n$▫ točkah, ki dosežejo maksimalno ter minimalno vrednost le-tega indeksa. Izkaže se, da so maksimizirajoči grafi sestavljeni iz poti, ki je na enem koncu identificirana s kliko podobne velikosti. Minimizirajoči grafi so sestavljeni iz treh poti podobne velikosti, ki imajo eno krajišče identificirano v skupni točki. Centralnostni indeksi skupin, vpeljani l. 1999 (Everett in Borgatti), merijo pomembnost izbrane množice vozlišč v omrežju. V disertaciji preučujemo skupinske indekse centralizacije ekscentričnosti, stopnje, ter vmesnostne centralnosti. Za skupine velikosti ▫$2$▫ določimo največje dosežene vrednosti skupinske ekscentričnosti ter skupinske vmesnostne centralnosti, hkrati pa določimo tudi pripadajoče ekstremalne grafe. Podobno določimo tudi za skupinsko centralnost stopnje, neodvisno od velikosti skupine. Na problem določanja najboljše skupine v smislu skupinske centralizacije stopnje pri podanem omrežju ▫$G$▫ se osredotočimo tudi algoritmično. Pri podani velikosti skupine k omenjeni problem prevedemo na problem maksimalne kdominacije, ter opazimo da je le-ta ▫${\mathcal NP}$▫-težak. Opišemo polinomski algoritem z najboljšim možnim aproksimacijskim koeficientom, ki za vse smiselne velikosti k izračuna centralizacijske vrednosti v skupni časovni zahtevnosti ▫${\mathcal O}(n^2)$▫. Omenjeni algoritem testiramo na šestih realnih omrežjih. V rezultatih opazimo lastnost unimodalnosti (za parameter ▫$k$▫), ki se lahko uporabi kot nova metoda za preučevanje velikih omrežij. Wienerjev indeks ▫$W(G)$ grafa $G$▫ je enak vsoti razdalj med vsemi pari vozlišč v ▫$G$▫. Z ▫$W[{\mathcal G}_n]$▫ označimo množico vseh vrednosti Wienerjevega indeksa za družino povezanih omrežij na ▫$n$▫ vozliščih, pri čemer največji neprekinjen interval iz ▫$W[{\mathcal G}_n]$▫ označimo z ▫$W^{\rm int}_n$▫. V disertaciji pokažemo, da je ▫$W^{\rm int}_n$▫ smiselno definiran ter se začne v vrednosti ▫${n \choose 2}$▫. Poleg tega pokažemo, da je velikost obeh ▫$W^{\rm int}_n$▫ ter ▫$W[{\mathcal G}_n]$▫ vsaj ▫${1 \over 6}n^3 + {\mathcal O}(n^2)$▫ tj.v večina vrednosti med ▫${n \choose 2}$▫ ter ▫${n+1 \choose 3}$▫ je vsebovana v ▫$W^{\rm int}_n$▫ (ter posledično tudi v ▫$W[{\mathcal G}_n]$▫).Type of material - dissertation ; adult, seriousPublication and manufacture - Ljubljana : [M. Krnc], 2015Language - englishCOBISS.SI-ID - 17452377
Link(s):
http://www.matknjiz.si/doktorati/2015/Krnc-14521-17.pdf
Repository of the University of Ljubljana – RUL
Digitalna knjižnica Slovenije - dLib.siDostop z namenskih računalnikov v prostorih NUK
Author
Krnc, Matjaž, 1987-
Other authors
Škrekovski, Riste
Topics
teorija grafov |
centralnost |
Freemanova centralizacija |
ekstremalni grafi |
skupinska centralnost |
graph theory |
centrality |
Freeman centralization |
extremal graphs |
group centrality
Library/institution |
City | Acronym | For loan | Other holdings |
---|---|---|---|---|
FMF and IMFM, Mathematical Library, Ljubljana | Ljubljana | MAKLJ |
reading room 1 cop.
|
|
National and University Library, Ljubljana | Ljubljana | NUK |
reading room 1 cop.
|
not for loan 1 cop.
|
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Krnc, Matjaž, 1987- | 34562 |
Škrekovski, Riste | 15518 |
Source: Personal bibliographies
and: SICRIS
Select pickup location:
Material pickup by post
Delivery address:
Address is missing from the member's data.
The address retrieval service is currently unavailable, please try again.
By clicking the "OK" button, you will confirm the pickup location selected above and complete the reservation process.
By clicking the "OK" button, you will confirm the above pickup location and delivery address, and complete the reservation process.
By clicking the "OK" button, you will confirm the address selected above and complete the reservation process.
Notification
Automatic login and reservation service currently not available. You can reserve the material on the Biblos portal or try again here later.
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
Pickup location | Material status | Reservation |
---|
Reservation in progress
Please wait a moment.
Reservation was successful.
Reservation failed.
Reservation...
Membership card:
Pickup location: