Contents

## 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

Facts about the Laplacian L73Proof:74

## Roy, John News Assignment Editor

Roy, John is from United States and they belong to KSAZ-TV and they are from Phoenix, United States got related to this Particular Journal. and Roy, John deal with the subjects like International News; Local News; National News; Regional News

## Journal Ratings by Green Mountain College

This Particular Journal got reviewed and rated by Green Mountain College and short form of this particular Institution is US and gave this Journal an Excellent Rating.