En social graf er en graf, hvis noder er repræsenteret af sociale objekter, såsom brugerprofiler med forskellige attributter (for eksempel: navn, fødselsdag, hjemby), fællesskaber , medieindhold og så videre, og kanterne er sociale forbindelser mellem dem [ 1] [2] .
En implicit social graf er en graf, der kan genereres (udledes, beregnes) baseret på brugerinteraktioner med deres "venner" og grupper af "venner" i et socialt netværk. I denne graf er der, i modsætning til den sædvanlige sociale graf, ingen eksplicit indikation af "venner", det vil sige, at der ikke er nogen åbenlyse sociale sammenhænge [3] .
Funktioner ved en social graf er karakteriseret ved sådanne metrics som: relationsmetrikker , forbindelsesmetrikker og segmenteringsmetrikker . For at løse problemer på en social graf, bruges specielle modeller, der kan bruges til at erstatte "rigtige" grafer . Ved hjælp af sociale grafer løser de sådanne problemer som: brugeridentifikation ; social søgning ; generering af anbefalinger om valg af "venner", medieindhold, nyheder og lignende ; afsløre "rigtige" forbindelser eller indsamle åben information til grafmodellering. Behandlingen af sociale grafdata er forbundet med en række problemer , såsom forskelle i sociale netværk , nærhed af sociale data .
I opgaver på en social graf bruges begrebet metrik - indikatorer, der numerisk viser karakteristika for sociale objekter, segmenter, grupper af objekter og deres relationer. Disse målinger bruges, når der udføres sociale netværksanalyser .
Relationsmålinger afspejler karakteren af forholdet mellem et socialt objekt og andre sociale objekter.
Homofili [4] er det omfang, i hvilket en bruger danner forbindelser med lignende mennesker. Lighed kan bestemmes af køn, alder, social status, uddannelsesniveau og så videre [5] .
Multiplicity - antallet af "flere" relationer, hvori brugere er [6] . For eksempel vil to brugere, der er venner og arbejder sammen, have en "mangfoldighed" på 2 [7] . "Multiple" er forbundet med "forbindelsens styrke."
Gensidighed - i hvilken grad brugere interagerer med hinanden, gengælder hinandens handlinger [8] . Netværksbeskyttelse er det omfang, i hvilket en brugers venner er venner med hinanden. Det kaldes også "et mål for fuldstændigheden af relationelle treklanger ". Antagelsen om, at brugeren er i netværkslukning, kaldes transitivitet . [9] . Naboskab - brugernes tendens til at have et stort antal forbindelser med geografisk tætte brugere [8] .
Linkmetrics afspejler funktionerne i links, både for individuelle sociale objekter og for grafen som helhed.
En bro er en bruger, hvis svage led udfylder "strukturelle huller", der giver en enkelt forbindelse mellem andre brugere eller klynger (grupper af brugere). Den korteste rute vil også passere gennem den [10] .
Centralitet - en grad, der viser "vigtigheden" eller "indflydelsen" af en bestemt bruger (brugerklynge) i grafen [11] [12] . Standardmetoderne til måling af centralitet er mediationscentralitet , nærhedscentralitet , egenvektorcentralitet , alfa-centralitet og gradcentralitet [13] .
Tæthed er andelen af direkte forbindelser i netværket i forhold til det samlede antal mulige [14] [15] . Afstand er det mindste antal links, der kræves for at etablere et forhold mellem to forskellige brugere. Strukturelle huller er manglen på forbindelser mellem to dele af netværket.
Forbindelsens styrke bestemmes af en lineær kombination af tid, nærhed og gensidighed [10] , jo større værdien af styrken af forbindelsen er, jo stærkere er den. Stærke bånd er defineret ved "homofili", "tilgrænsende" eller "transitivitet", mens svage bånd er defineret af "broer".
Segmenteringsmålinger afspejler egenskaberne ved en social graf opdelt i segmenter, der har karakteristiske træk.
En klike er en gruppe, hvor alle brugere har "direkte" forbindelser (hjørnepunkter er forbundet (forbundet) med en kant) til hinanden [16] . En omgangskreds er en gruppe, hvor "direkte" forbindelser mellem brugere ikke er påkrævet [17] .
Klyngekoefficienten er graden af sandsynlighed for, at to forskellige brugere tilknyttet et bestemt individ også er tilknyttet. En høj clusteringskoefficient indikerer en høj gruppelukning, med andre ord kan gruppen være en "klike".
Samhørighed er den grad, hvori brugere er forbundet af et fælles bånd, der danner social sammenhængskraft . Strukturel sammenhængskraft - angiver en sådan enkelt struktur i gruppen, at fjernelse af et lille antal brugere fører til en pause i gruppen [16] .
Nogle velkendte grafmodeller kan erstatte "rigtige" sociale grafer [18] .
Funktionelt drevne modeller sigter mod at reproducere de statistiske karakteristika af en graf, såsom magt-lovfordeling og dynamiske ændringer i grafens tæthed, såsom Barabasi-Albert- modellen og den brændende skov -model .
Forsætligt kontrollerede modeller er fokuseret på at efterligne processen med at skabe den originale graf, denne klasse af modeller inkluderer tilfældig gennemkøring og tilfældige gåture, den nærmeste nabomodel.
Strukturdrevne modeller fanger statistiske data fra strukturen af en graf, hvilket gør det muligt for den tilsvarende generator at reproducere tilfældige grafer med de samme strukturelle begrænsninger, sådanne modeller inkluderer Kronecker-grafer , dK-grafer .
Brugeridentifikation - påvisning af profiler tilhørende en person i flere sociale netværk [19] . Løsning af dette problem giver mulighed for at opnå en mere komplet social graf, som kan være nyttig i mange opgaver såsom social søgning og generering af anbefalinger .
Søg efter sociale objekter (brugere, deres data, deres registreringer og så videre) baseret på analysen af et sæt links, der indeholder de ønskede objekter [20] .
En vigtig opgave er at finde præcise algoritmer til at generere anbefalinger og tilbud til brugerne, som også bruges til at lave en interessegraf baseret på en social graf. Det kan være anbefalinger fra venner (brugere opdeler sjældent deres kontakter i sociale grupper, men ikke desto mindre opdeler de implicit disse kontakter i klynger gennem deres interaktioner inden for det sociale netværk [21] ), indholdsanbefalinger (anbefalinger af medieindhold, fællesskaber, nyheder mv. .) yderligere [22] [ angiv link ] ). Der er traditionelle tilgange i anbefalingssystemer [23] [ specificer link ] :
En separat udfordring er at anvende " open source-intelligens "-tilgangen til at identificere sande forbindelser mellem brugere, dvs. rigtige venner, slægtninge og så videre [25] .
Konstruktion af en social graf baseret på data opnået som et resultat af parsing af webtjenester fra sociale netværksudbydere.
Følgende kriterier er opstillet for at evaluere opgaven [26] :
Valget af noder spiller en vigtig rolle i traversal: noder er udgangspunktet for traversalen, det er vigtigt at vælge de rigtige noder og traversal kørækkefølge for at undgå dårlig sidekvalitet. Nodevalgsalgoritmer bestemmer, hvilken node der skal vælges næste gang, blandt de anvendte algoritmer er bredde-først søgning , en gruppe af grådige algoritmer .
På grund af tætheden af sociale data kan du springe det meste af den sociale graf over, forskellige bypass-algoritmer påvirker sådanne brugere på forskellige måder. Derudover har forskellige sociale netværk forskellige unikke egenskaber, selvom de leverer lignende tjenester, hvilket også komplicerer opgaven med at indsamle information.
For problemet med brugeridentifikation er hovedproblemet forskellene i sociale netværk. Semantikken af relationer mellem sociale objekter og sociale grafer af forskellige topologier [27] [ specificer link ] spiller hovedsageligt en rolle .
Hovedproblemet med at generere anbefalinger er problemet med koldstart - beregning af anbefalinger for nye sociale objekter (brugere, indlæg, medieindhold og så videre) [28] [ specificer link ] .
Hovedproblemet med at indsamle data til den sociale graf er nærheden af sociale netværk [29] . For det første er det vanskeligt at få en social graf fra "leverandører" [30] på grund af værdien og den juridiske beskyttelse af sociale data. For det andet er den store vanskelighed indsamlingen af millioner af kontaktlister, profiler, fotos, videoer og lignende indhold af skrabere . Mange sociale medier "udbydere" bruger en enkelt side model eller mange dynamiske sider indeholdende Ajax og DHTML , hvilket også skaber en masse problemer for at skabe en fleksibel parser.