# Analysis of Large Graphs Community Detection Q : What do these large graphs present Q : How can we find the partitions

## Analysis of Large Graphs Community Detection Q : What do these large graphs present Q : How can we find the partitions

Roy, John, News Assignment Editor has reference to this Academic Journal, PHwiki organized this Journal Analysis of Large GraphsCommunity DetectionBy:KIM HYEONGCHEOL WALEED ABDULWAHAB YAHYA AL-GOBIMUHAMMAD BURHAN HAFEZSHANG XINDI HE RUIDAN 1OverviewIntroduction & MotivationGraph cut criterion Min-cutNormalized-cutNon-overlapping community detectionSpectral clusteringDeep auto-encoderOverlapping community detectionBigCLAM algorithm2Intro to Analysis of Large GraphsIntroductionObjective1KIM HYEONG CHEOL

This Particular University is Related to this Particular Journal

IntroductionWhat is the graphDefinitionAn ordered pair G = (V, E)A set V of verticesA set E of edges A line of connection between two vertices2-elements subsets of VTypesUndirected graph, directed graph, mixed graph, multigraph, weighted graph in addition to so on4IntroductionUndirected graphEdges have no orientationEdge (x,y) = Edge (y,x)The maximum number of edges : n(n-1)/2All pair of vertices are connected to each otherUndirected graph G = (V, E)V : {1,2,3,4,5,6}E : {E(1,2), E(2,3), E(1,5), E(2,5), E(4,5) E(3,4), E(4,6)}5IntroductionThe undirected large graphE.g) Social graph Graph of Harry potter fanfiction A sampled user email-connectivity graph : http://research.microsoft.com/en-us/projects/S-GPS/Adapted from http://colah.github.io/posts/2014-07-FFN-Graphs-Vis/6

IntroductionThe undirected large graphE.g) Social graph Graph of Harry potter fanfiction A sampled user email-connectivity graph : http://research.microsoft.com/en-us/projects/S-GPS/Adapted from http://colah.github.io/posts/2014-07-FFN-Graphs-Vis/Q : What do these large graphs present7MotivationSocial graph : How can you feel A sampled user email-connectivity graph : http://research.microsoft.com/en-us/projects/S-GPS/VS8MotivationGraph of Harry potter fanfiction : How can you feelVSAdapted from http://colah.github.io/posts/2014-07-FFN-Graphs-Vis/9

MotivationIf we can partition, we can use it as long as analysis of graph as below 10MotivationGraph partition & community detection11MotivationGraph partition & community detection12

MotivationGraph partition & community detectionPartitionCommunity13MotivationGraph partition & community detectionPartitionCommunityQ : How can we find the partitions14Criterion : Graph partitioningMinimum-cutNormalized-cut2KIM HYEONG CHEOL

Criterion : Basic principleA Basic principle as long as graph partitioningMinimize the number of between-group connectionsMaximize the number of within-group connectionsGraph partitioning : A & B16Criterion : Min-cut VS N-cutA Basic principle as long as graph partitioningMinimize the number of between-group connectionsMaximize the number of within-group connections Minimum-Cut vs Normalized-Cut 17Mathematical expression : Cut (A,B)For considering between-group 18

Mathematical expression : Vol (A)For considering within-groupvol (A) = 5vol (B) = 519Criterion : Min-cutMinimize the number of between-group connectionsminA,B cut(A,B)Cut(A,B) = 1 -> Minimum valueAB20Criterion : Min-cutCut(A,B) = 1ABABBut, it looks more balanced How21

Criterion : N-cutMinimize the number of between-group connectionsMaximize the number of within-group connectionsIf we define ncut(A,B) as below, -> The minimum value of ncut(A,B) will produces more balanced partitions because it consider both principles22MethodologyABABVS23SummaryWhat is the undirected large graphHow can we get insight from the undirected large graphGraph Partition & Community detectionWhat were the methodology as long as good graph partitionMin-cutNormalized-cut24

Spectral ClusteringDeep GraphEncoder3 Non-overlapping community detection: Waleed Abdulwahab Yahya Al-GobiFinding ClustersHow to identify such structureHow to spilt the graph into two piecesNodesNodesAdjacency MatrixNetwork26Spectral Clustering AlgorithmThree basic stages:1) Pre-processingConstruct a matrix representation of the graph2) DecompositionCompute eigenvalues in addition to eigenvectors of the matrixFocus is about in addition to it corresponding . 3) GroupingAssign points to two or more clusters, based on the new representation27

Matrix RepresentationsAdjacency matrix (A):n n binary matrixA=[aij], aij=1 if edge between node i in addition to j28Matrix RepresentationsDegree matrix (D):n n diagonal matrixD=[dii], dii = degree of node i29Matrix RepresentationsHow can we use (L) to find good partitions of our graph What are the eigenvalues in addition to eigenvectors of (L)We know: L . x = . x 30