En social graf är en graf vars noder representeras av sociala objekt, såsom användarprofiler med olika attribut (till exempel: namn, födelsedag, hemstad), gemenskaper , mediainnehåll och så vidare, och kanterna är sociala länkar mellan dem [ 1] [2] .
En implicit social graf är en graf som kan genereras (härledas, beräknas) baserat på användarinteraktioner med deras "vänner" och grupper av "vänner" i ett socialt nätverk. I denna graf, till skillnad från den vanliga sociala grafen, finns det ingen explicit indikation på "vänner", det vill säga det finns inga uppenbara sociala kopplingar [3] .
Funktioner i en social graf kännetecknas av sådana mått som: relationsmått , anslutningsmått och segmenteringsmått . För att lösa problem på en social graf används speciella modeller som kan användas för att ersätta "riktiga" grafer . Med hjälp av sociala grafer löser de sådana problem som: användaridentifiering ; social sökning ; generering av rekommendationer om val av "vänner", mediainnehåll, nyheter och liknande ; avslöja "riktiga" samband eller samla in öppen information för grafmodellering. Bearbetningen av sociala grafdata är förknippad med ett antal problem , såsom skillnader i sociala nätverk , närhet till sociala data .
I uppgifter på en social graf används begreppet mått - indikatorer som numeriskt visar egenskaperna hos sociala objekt, segment, grupper av objekt och deras relationer. Dessa mätvärden används vid analys av sociala nätverk .
Relationsmått återspeglar karaktären av förhållandet mellan ett socialt objekt och andra sociala objekt.
Homofili [4] är i vilken utsträckning en användare bildar kopplingar till liknande personer. Likhet kan bestämmas av kön, ålder, social status, utbildningsnivå och så vidare [5] .
Multiplicity - antalet "flera" relationer där användare är [6] . Till exempel kommer två användare som är vänner och arbetar tillsammans att ha en "mångfald" på 2 [7] . "Multiple" förknippas med "anslutningens styrka".
Ömsesidighet - graden i vilken användare interagerar med varandra, återger varandras handlingar [8] . Nätverksintegritet är i vilken utsträckning en användares vänner är vänner med varandra. Det kallas också "ett mått på fullständigheten av relationstriader ". Antagandet att användaren är i nätverksstängning kallas transitivitet . [9] . Grannskap - användarnas tendens att ha ett stort antal kontakter med geografiskt nära användare [8] .
Länkmått återspeglar egenskaperna hos länkar, både för enskilda sociala objekt och för grafen som helhet.
En brygga är en användare vars svaga länkar fyller "strukturella hål", vilket ger en enda anslutning mellan andra användare eller kluster (grupper av användare). Dessutom kommer den kortaste rutten att passera genom den [10] .
Centralitet - en grad som visar "viktigheten" eller "inflytandet" av en viss användare (kluster av användare) i grafen [11] [12] . Standardmetoderna för att mäta centralitet är mediationscentralitet , proximity centrality , egenvektorcentralitet , alfacentralitet och gradcentralitet [13] .
Densitet är andelen direktanslutningar i nätet i förhållande till det totala antalet möjliga [14] [15] . Avstånd är det minsta antal länkar som krävs för att upprätta en relation mellan två distinkta användare. Strukturella hål är bristen på anslutningar mellan två delar av nätverket.
Förbindelsens styrka bestäms av en linjär kombination av tid, närhet och ömsesidighet [10] , ju större värdet på styrkan i sambandet är, desto starkare är den. Starka band definieras av "homofili", "angränsning" eller "transitivitet", medan svaga band definieras av "broar".
Segmenteringsmått återspeglar egenskaperna hos en social graf uppdelad i segment som har utmärkande egenskaper.
En klick är en grupp där alla användare har "direkta" kopplingar (hörn är anslutna (anslutna) med en kant) till varandra [16] . En umgängeskrets är en grupp där "direkta" kopplingar mellan användare inte krävs [17] .
Klustringskoefficienten är graden av sannolikhet att två olika användare associerade med en viss individ också är associerade. En hög klustringskoefficient indikerar en hög gruppslutning, med andra ord kan gruppen vara en "klick".
Sammanhållning är den grad i vilken användare är sammanlänkade genom ett gemensamt band, vilket bildar social sammanhållning . Strukturell sammanhållning - indikerar en sådan enskild struktur i gruppen att avlägsnandet av ett litet antal användare leder till ett avbrott i gruppen [16] .
Vissa välkända grafmodeller kan ersätta "riktiga" sociala grafer [18] .
Funktionellt drivna modeller syftar till att reproducera de statistiska egenskaperna hos en graf, såsom kraftlagsfördelning och dynamiska förändringar i grafdensitet, såsom Barabasi-Albert- modellen och den brinnande skogsmodellen .
Avsiktligt kontrollerade modeller är fokuserade på att emulera processen att skapa den ursprungliga grafen, denna klass av modeller inkluderar slumpmässig genomgång och slumpmässiga promenader, den närmaste grannmodellen.
Strukturdrivna modeller fångar statistiska data från strukturen av en graf, vilket gör att motsvarande generator kan reproducera slumpmässiga grafer med samma strukturella begränsningar, sådana modeller inkluderar Kronecker-grafer , dK-grafer .
Användaridentifiering - upptäckt av profiler som tillhör en person i flera sociala nätverk [19] . Genom att lösa detta problem kan en mer komplett social graf erhållas, vilket kan vara användbart i många uppgifter som social sökning och rekommendationsgenerering .
Sök efter sociala objekt (användare, deras data, deras register och så vidare), baserat på analysen av en uppsättning länkar som innehåller de önskade objekten [20] .
En viktig uppgift är att hitta korrekta algoritmer för att generera rekommendationer och erbjudanden till användare, vilket också används för att skapa en intressegraf baserad på en social graf. Det kan vara rekommendationer från vänner (användare delar sällan in sina kontakter i sociala grupper, men ändå delar de implicit in dessa kontakter i kluster genom sina interaktioner inom det sociala nätverket [21] ), innehållsrekommendationer (rekommendationer av medieinnehåll, gemenskaper, nyheter, etc.) .) vidare [22] [ specificera länk ] ). Det finns traditionella tillvägagångssätt i rekommendatorsystem [23] [ specificera länk ] :
En separat utmaning är att tillämpa " open source intelligence "-metoden för att identifiera verkliga kopplingar mellan användare, dvs riktiga vänner, släktingar och så vidare [25] .
Konstruktion av en social graf baserad på data som erhållits som ett resultat av att analysera webbtjänster från leverantörer av sociala nätverk.
Följande kriterier är satta för att utvärdera uppgiften [26] :
Valet av noder spelar en viktig roll vid traversering: noder är startpunkten för genomgången, det är viktigt att välja rätt noder och korsningsköordning för att undvika dålig sidkvalitet. Nodvalsalgoritmer bestämmer vilken nod som ska väljas härnäst, bland de algoritmer som används är bredd-först sökning , en grupp giriga algoritmer .
På grund av närheten till sociala data kan du hoppa över det mesta av den sociala grafen, olika bypass-algoritmer påverkar sådana användare på olika sätt. Dessutom har olika sociala nätverk olika unika egenskaper, även om de tillhandahåller liknande tjänster, vilket också försvårar uppgiften att samla in information.
För problemet med användaridentifiering är det största problemet skillnaderna i sociala nätverk. Semantiken för relationer mellan sociala objekt och sociala grafer för olika topologier [27] [ specificera länk ] spelar huvudsakligen en roll .
Huvudproblemet med att generera rekommendationer är problemet med kallstart - beräkning av rekommendationer för nya sociala objekt (användare, inlägg, mediainnehåll och så vidare) [28] [ specificera länk ] .
Det största problemet med att samla in data för den sociala grafen är närheten till sociala nätverk [29] . För det första är det svårt att få en social graf från "leverantörer" [30] på grund av sociala datas värde och rättsliga skydd . För det andra är den stora svårigheten insamlingen av miljontals kontaktlistor, profiler, foton, videor och liknande innehåll av skrapor . Många "leverantörer" av sociala medier använder en enkelsidesmodell eller många dynamiska sidor som innehåller Ajax och DHTML , vilket också skapar en hel del problem för att skapa en flexibel parser.