NetworkX & 그래프 데이터 사이언스

intro 은 기업의 정보시스템에 축적되는 데이터들(일반적으로 이 분야에서는 이벤트 로그라는 이름으로 많이 부릅니다)로부터 회사의 업무 간의 흐름을 도출해 내고, bottleneck 등을 발견하는 기술을 의미합니다. 몇 년 전부터는 단지 프로세스...

Problem 는 2 dimensional array로, 가 1이면, node 가 연결되어 있음을 의미한다(o/w 0) connections를 이용하여 네트워크를 그릴 수 있으며, 입력받은 connections의 경우 모든 노드가 연결되어 있다....

intro 보통 python에서 그림을 그릴 때는 을 사용해서 그리는 일이 많기는 합니다만, 네트워크를 그릴때는 생각만큼 예쁘게 나오지 않는 일들이 많습니다. 그래서 찾아보니 를 이용하면 좀 예쁘게 르리 수 있다는 것 같아서 이를 어떻게 사용할 ...

centrality는 무엇인가요? 한국말로 하면 '중심도'가 되겠네요. 네트워크가 구성되었을 때, 우리가 궁금한 것은 네트워크에서 어떤 노드가 중요한 놈인가? 라는 것입니다. 란 네트워크 상에서 중요한 노드를 찾기 위한 일종의 metric이라고 ...

scopus 데이터를 이용한 저자 키워드 데이터 자동화하기 물론 '텍스트'를 다루는 대부분의 분석의 경우는 자동화가 어렵습니다. 다양한 이유가 있겠으나, 제가 아는 범주에서의 문제는 '예외처리'죠. 텍스트는 예외가 많습니다. 특히, 키워드 분석을...

백업용으로 일단 업로드 해두었습니다. 아래 내용은 graphviz를 이용해 그림을 그려보았으나, 생각보다 예쁘게 나오지 않았씁니다. 원인은 다음들이라고 생각됩니다. - dot language를 잘 모르고 주먹구구식으로 함 - 체계적으로 코딩한 것...

maplotlib를 사용하는 이유. 이전 포스트에서는 를 사용하겠다고 했었습니다. 물론 이 것의 장점이 있기는 한데, 약간 범용적인 측면에서 생각해보면 결국 matplotlib로 돌아가게 됩니다(물론 process model을 표현하는데는 gra...

간단히 말해서, 네트워크 또한 데이터 구조다. '어떤 노드가 어떤 노드와 연결되어 있는가?', '또한 그 노드들은 어떠한 특성을 가지고 연결되어 있는가?', '그 노드와 직접 연결된 노드들은 무엇이 있는가?' 등 네트워크를 분석하다보면 관련된 분...

사실 해보니까 매우 간단하네요. 예전에도 이걸 정리를 해뒀던 것 같은데, 매번 여기저기 둬서 없어졌습니다. 괜히 node size, edge width를 weight에 따라서 알아서 조절하려고 하지 말고, 그냥 cmap을 이용해서 간단하게 하는 ...

훨씬 깔끔하게 만든 rnd knowlege map code 아 이제 뭘 좀 고치거나 확장하거나 하는게 좋겠네요(물론 이전과의 비교지, 지금도 문제는 많습니다만)) 앞으로도 이 내용은 계속 수정하면서 올릴 것 같습니다. 기존의 문제점 일단 제대로 ...

bipartite graph를 다뤄 봅시다. author keyword 와 index keywords 는 서로 다른 의미를 가집니다. 하나의 논문에는 author keyword와 index keyword가 둘 다 있는데, 이 edge를 중심으로 ...

작업일지 제가 궁극적으로 하려는 것은 '저자 키워드'를 필터링 하려는 것입니다. 'small and medium enterprise' 와 'sme'는 같은 의미를 가집니다. 그렇다면 이 두 가지가 모두 표현될 필요는 없겠죠. 따라서 이를 변환하고...

일반적으로 쓰는 networkx 의 function들은 centrality, draw, add/remove node and edges 가 다인데, 이 외에도 꽤나 유용한 함수들이 많이 있습니다. 이것들을 좀 정리해두는 것이 필요하다고 생각됨. n...

네트워크 상에서 비슷한 역할을 하는 노드를 찾아봅시다! structural equivalence, '구조적 등위성'으로 표현할 수 있을텐데, 네트워크 상에서의 연결성을 확인해보면, 두 노드가 '의미적으로 비슷하다'는 것을 의미하는 성질입니다. 대...

후 키워드 네트워크부터 다시 합시다. 데이터 전처리부분은 거의 다 한 것 같아요. 맨 끝에 설명하겠습니다. 이제는 정말 단일한 데이터 집단을 모은게 아닐까 싶습니다. 키워드 네트워크를 구성했을 때, 만든 네트워크에서 잘못된 노드 들이 있는 경우가...

네트워크를 다양한 레이아웃에 따라서 2차원에 그리기. 에서 , 등으로 그림을 그릴 때는 이미 axis에서 어떤 좌표에 그림을 그리면 될지가 명확하게 나와 있습니다만, network에서는 개별 node에 좌표값이 없기 때문에 어디에 그려야 하는지 ...

아주 간단합니다. 사실 너무 간단해서 굳이 이걸 포스팅할 필요가 있는가 라는 생각도 들긴 하는데..... 다음처럼 해당 node의 정보값(정확히는 attr dictionary)에 그대로 넣어주면 됩니다. 단 edge는 tuple이 key값으로 들어감

네트워크에서 community 찾기 일단 이건 일종의 clustering이라고 생각하셔도 상관없습니다. 일단 점과 선으로 된 네트워크를 구성했을 때, 비슷한 집단끼리 묶어보고싶잖아요. 전체 네트워크만 보는 건 큰 의미가 없으니까 이걸 좀 비슷한 ...

bipartite graph bipartie graph는 set A와 set B 간에는 연결되는데, A의 node a들 끼리 연결되거나, B의 node b들 끼리 연결되는 일이 없는 경우를 말합니다. 예를 들면, set A는 사람이고, set B...

havelhakimigraph networkx에 라는 랜덤한 bipartite 그래프 생성기가 있습니다. 만약 bipartite set가 각각 5개, 3개 라면, 그 크기의 각 node의 deg sequence를 넘겨주면 그 deg들에 맞는 gr...

노드를 바꿔주기 networkx에는 꽤 괜찮은 random graph generator들이 많이 있습니다. 단 만들 때부터 node set를 정하고 만들기는 조금 어려워요. 그렇다면 일단 만든 다음에 바꿔주면 됩니다 하하핫 쉽죠. 바꿔주는 방법이...

DiGraph DiGraph는 방향성이 있는 네트워크를 말합니다. 일반적인 graph라면 edge를 그냥 그리면 되는데, 방향성이 있는 graph는 화살표를 잘 그려줘야 합니다. arrow style은 여기에 볼 수 있는데, 각각 어떻게 나오는지...

random tree 만들기 random tree를 만들거에요. tree라는 것은 parent, children를 가지는 스트럭쳐죠. 저는 parent, children로 node를 접근하는 건 만들지 않았습니다만, random 하게 tree를 ...

인간관계를 분석합니다. 이번에 파이콘 한국 2018에서 발표하게 되어 발표자료를 준비하고 있습니다. 일단 여기에는 그림은 들어가지 않을 예정이고, 코드만 정리해서 보여줄 예정입니다. 발표자료는 여기서 보실 수 있습니다. 아무래도 필요한 부분들을 ...

tree에 적합한 layout을 찾습니다. networkx에는 다양한 layout이 있습니다만, tree 구조에 적합한 레이아웃은 없어요(정확히는 없다고 생각했습니다). 그런데 사실 없다는게, 제 입장에서는 말이 안되서 한참 찾았는데, 찾다보니 ...

random하게 tree를 만듭니다. 예전에 제가 직접 random하게 tree를 만들어주는 코드를 만들었습니다. random하게 각 level별 node의 수를 정하고 children의 수도 랜덤하게 정해서 진행했는데, 생각보다 만드는데 시간이...

rescaling layout networkx로 네트워크를 시각화할 때 다양한 layout을 씁니다. 보통 쓰는 spring, spectral, shell 등의 레이아웃에는 문제가 없는데, 아래와 같은 layout을 사용할때는 0.0과 1.0사이...

tree에서 Root 찾기 networkx의 를 사용해서 tree를 만들고 관리하는데, 그때 적절한 root를 찾는 것이 중요해요. 또 해당 root를 중심으로 다른 node들이 얼마나 멀리 떨어져 있는지를 파악하는 것도 중요하구요. 그래서 아래...

jupyter notebook에 그림을 넣고 싶어요. graphviz로 그림을 만드는 함수를 다음처럼 정의했습니다. 그런데, 저는 경우에 따라서 한 셀 내에서 여러 그림을 동시에 보여주려고 하고 있거든요. 따라서 다른 방법을 모색했습니다. usi...

간단합니다. 보통 때는 상관이 없는데, tree 구조를 그릴 때는 graphviz의 레이아웃이 그림이 더 이쁘거든요. 그래서 간단하게 변경하는 코드를 추가합니다. 두잇 간단합니다. 밑에 주석처리한 코드는 그림을 원하는 곳에 저장하고 싶을 때 씁니...

edit-distance "abc", "abcd"는 얼마나 비슷할까요? 혹은 정량적으로 어떻게 비슷한 정도를 측정할 수 있을까요? 간단하게 두 스트링을 비교해보면 캐릭터 하나만 추가되어있는 것을 알 수 있습니다. 즉, '하나만 지우면 같아질 것 ...

intro 최근에 networkx github에 이슈를 하나 날렸습니다. networkx의 모든 layout(spring, shell 등)은 딕셔너리(key: node label, value: (x, y))로 리턴이 되는데, 이라는 함수는 np....

compose network with weight 모든 네트워크를 합쳐서 관리하는 것이 아니라, 분리해서 관리하다가, 필요할때만, 네트워크를 합쳐서 관리하는 것이 더 효율적일 때가 있습니다. 예를 들어서, 연도별로 네트워크를 따로 보는 것이 필요...

intro 저는 networkx를 활용해서 네트워크를 그리고, 분석하고, 또 만들고 아무튼 잡일을 아주 많이 합니다. 그런데 네트워크를 그린 다음, 해당 네트워크에서 특정 node A와 특정 node B가 연결되어 있는지 확인하는 방법을 정리했습...

intro 이제는 와 를 너무 많이 사용해서, 이 둘을 사용해서 그림을 그릴 때가 편할때가 있습니다만, 가끔 의 layout을 이용해서 그림을 그려주고 싶을 때가 있습니다. 대략 아래 그림처럼 뭔가 binary tree같은 애들을 그려주기가 편하...

intro 를 어렵게 구축했다면, 해당 그래프를 일정한 파일 포맷으로 저장해두어야 다음에 쓰기가 편할 수 있습니다. 따라서, 여기서는 graph를 어떻게 저장하고, 다시 저장한 그래프를 불러오는지를 정리합니다. Graph formats graph...

bokeh로 network 그리기. 저는 네트워크 분석을 주로 수행합니다. 따라서 네트워크를 시각화할 필요성이 많은데, 를 이용해서 그림을 그릴 때는 비교적 쉽게 그림을 그릴 수 있습니다. 이를 활용해서 png, svg의 형태로 그림을 뽑아내는 ...

graph의 isomorphic을 체크해봅시다. 아래와 같이, 두 개의 그래프가 있다고 합시다. 이 둘은 노드도, edge도 모두 동일합니다. 이 두 그래프가 같은지를 확인하려면 어떻게 하면 될까요? 우리가 흔히 쓰는 것처럼 을 써서 처리하면 될...

network equivalence, isomorphism. 얼마전에, network의 isomorphic을 체크한다는 글을 썼었습니다만. 과 는 다릅니다. 이걸 모르고 글을 쓴 것 같네요. network isomorphism graph isom...

random walk generation random walk라 함은, 말 그대로 무작위로 이리저리 움직이는 것을 말합니다. 이걸 그래프에서 이야기하자면, 주어진 그래프에서 정의한 노드와 엣지의 특성에 맞춰서 이런저런 시퀀스를 만드는 것을 일종의...

최근에 네트워크의 노드를 벡터로 변환하는 작업을 수행하고 있습니다. "왜 잘 있는 노드를 벡터로 변환해?"라고 말씀하실 수도 있는데, 이건, 기존의 많은 ML/DL 라이브러리들이 숫자에 기반하기 때문이죠. 즉, Graph를 숫자로 변환했을때, 더...

최근에는 GQL이라는 Graph Query Language를 정리했습니다. 결국 데이터를 Graph로서 표현하고, 이를 필요에 따라서, 필터링해서 볼 수 있는 쿼리언어 표준을 만들자! 라는 것이 해당 언어의 목적이죠. 저는, 그렇게까지 대용량의 ...

network에서 clique를 뽑고, 사용하는 방법. 솔직히, 저는 clique를 잘 뽑지 않습니다. 보통의 일반적인 네트워크들은, 생각보다 dense하지 않고, girvan-newman 방법을 이용하는 것이 훨씬 효율적일 때가 많거든요. 즉 ...

물론, 굳이 networkx로 가져올 필요가 있는가? 물론, 기본적으로 DB에 잘 정리되어 있는 데이터를, 그리고 심지어 보통 이곳에 있는 데이터들은 로컬로 가져오기에는 지나치게 큰 크기의 데이터인 경우가 대부분인데, 이 데이터를 로컬로 가져와서...

intro 본문에서는 python에서 GraphDB인 neo4j와 어떻게 연결하고, 쿼리를 전송하고 그 응답을 받는 기본적인 방식을 정리하였습니다. python을 GraphDB인 neo4j와 연결하여 처리하는 방법을 정리합니다. 참고로 저는 ne...

Neo4j - Introduction to Neo4j에 대한 part 7개를 각각 다음과 같이 정리하였습니다. 1. neo4j : part 1 : Introduction to Graph Databases. 1. neo4j : part 2 : In...

요즘은 networkx에서 community detection에 대해서 정리하고 있습니다. 테크닉들에 대해서 테스트를 해보려면, 클러스터가 몇 개로 구성된 예제그래프가 필요합니다. 그리고, 당연히도, 에서 이러한 예제 그래프를 지원하죠. 위와 같...

Error: 'AtlasView' object does not support item assignment 로 코딩을 하다보면 종종 뜨는 에러 중에서 다음의 에러가 있습니다. 에러 코드를 그대로 해석하자면 "AtlasView 오브젝트는 item a...

Graph로부터 subgraph를 만들어봅시다. Graph를 분석하다보면, 필요에 따라서, subGraph를 만들어야 할 때가 있습니다. 이럴 때는 두 가지 방식이 있는데, 와 이미 가진 graph object인 의 class method로 접근...

node, edge의 attribute를 업데이트하자. 대상을 graph로 표현한 다음 필요에 따라서 각 graph의 node, edge의 attribute를 업데이트합니다. 필요에 따라서, weight, centrality 등 다양한 값들을 업...

Graph에서 Node간의 연결성을 확인하기 위해서는, AtlasView로 접근하는 것이 훨씬 빠르다. 대상을 그래프로 관리하고 있을 때, 많이 활용하게 되는 것으로는, 과 가 연결되어 있는가 연결되어 있지 않은가? 입니다. 같은 말이지만 "이 ...

networkx - approximation for NODE connectivity Graph는 기본적으로 빠르게 처리하는 것이 어렵습니다. 테이블과 같은 형태라면, 비교적 어느 정도 병렬적으로 처리할 수 있는데(서로 데이터가 독립적이기 때문),...

K - component. 는 graph 가 있을 때, 모든 node의 local node connectivity가 최소한 k인, maximal subgraph를 말한다("maximal"은 "만들 수 있는 최대의 그래프"라고 해석하면 될텐데, s...

Average clustering coefficient of Graph. background local clustering of each node 는 각 노드에 대한 clustering(밀집도)를 말하며, 해당 노드 이웃들과 구성할 수 있는 모든...

networkx - Degree Centrality. 는 각 node에 직접 연결된 node의 수를 말한다. 아주 단순히 봤을 때, 이 값이 클수록 해당 노드가 그래프에서 가지는 직접적인 영향력이 큰 것은 자명하며, 이 값을 중심으로 node의 ...

What is Clique? clique는 maximal complete subgraph(모든 node pair 간에 edge가 있는 subgraph)라고 생각하시면 됩니다. ㅇ 가령, 노드 A, B, C가 있을 때, 서로 모두 연결되어 있다면(...

Eigen Value and Vector: 분명히 학부 때 배웠던 것입니다만. 제 기억이 맞다면, 2008년(아 너무 먼 옛날이다)에 학교 "선형 대수학(Linear algebra)"에 분명히 배웠던 기억이 있습니다. 물론 아주 엄청나게 예전이고...

Eigenvector centrality는 일반적으로 네트워크 내 노드들의 영향력을 측정하기 위해 사용되는데, 직접적인 영향력만을 반영하며, 노드간의 차이를 구별하지 않는 degree cetrality와 다르게, "중요한 노드(네트워크 내에서 영...

line summary 각 node가 어떤 community에 속하는지를 고려하여 CN(Common neighbor)와 RA(Resource Allocation Index)를 보정함. 2012년 프로시딩에서 발표했던 논문인 Using commun...

Centrality - Closeness Centrality closeness centrality는 흔히, "근접 중심성"이라고 말하는데, "어떤 Node A에서 다른 모든 노드(reachable nodes)에 도달하기 위한 최단거리의 길이(sh...

Katz Centrality는 Network 내 Node의 중심성(centrality)를 측정하기 위한 방법 중 하나입니다. 다른 centrality measure들과는 다르게, node pair간의 path를 고려하여 영향력을 측정합니다. 가령...

간단한 선형 방정식 풀기. 간단한 선형방정식()을 풉니다. 단, a는 diagonal matrix(rectangular matrix)여야 하죠. 를 사용해야 하죠.

current flow betweenness centrality. 이전에, closeness centrality를 이야기할 때도, 라는 이름으로, 측정한 것이 있었죠. betwenness centrality도 마찬가지로, 전류 모형을 적용하여, ...

는 "G의 모든 node pair의 최단 거리에, node V가 얼마나 많이 포함되는지를 비율로 표현하여, node V가 전체 그래프의 흐름에 얼마나 영향을 미치는지"를 측정하는 지표입니다. 즉, 계산 방법은 다음처럼 간단하죠 1) 모든 node...

edge betweennss centrality "edge betwenness centrality"는 node betweenness centrality와 유사한데, "node"를 shortest path의 비율을 계산하는 것이 아니라, edge를...

Information Centrality 는 "Current Flow Closeness Centrality"라고도 부릅니다. 여기서 "Current"는 "전류"를 가리키죠. 즉 "전류 흐름에 근거한 근접 중심성 분석"이라는 말이 되죠. 흔히들 네...

What is Line Graph? Line Graph는 그냥 "Node를 Edge로 Edge를 Node로 변형한 그래프를 말합니다". 가령, edge들이 로 존재하는 그래프(Node: 0, 1)의 Line Graph는 로, edge가 하나뿐인 ...

: "Node, edge가 반복되어도 상관없으며, graph에서 발생할 수 있는 - : walk중에서 source와 target이 같은 경우. - : walk 중에서 source와 target이 다른 경우. : "edge가 반복되지 않는" wal...

Centrality - communicability betweenness centrality 전통적인 개념에서는 network를 분석할 때, shortest path만을 고려하게 됩니다. 하지만, 이는 실재적인 graph의 특성을 반영하지 못하죠...

centrality - group betweenness centrality node betweenness centrality는 "그래프의 모든 node pair 간의 shortest path 중에서 node 을 지나는 최단거리의 비율"을 말하죠....

What is communicability? networkx documentation에 작성된 의미에 따르면, 다음과 같습니다. The communicability between pairs of nodes in G is the sum of clo...

centrality - harmonic centrality. harmonic centrality는 다른 모든 노드들인 v들로부터, 해당 노드인 u까지 향하는 "최단 거리의 길이(shortest path length)의 역수"를 모두 더한 값을 말...

What is subgraph centrality? subgraph centrality는 "node가 graph의 subgraph에 속할 비율"을 말합니다. subgraph의 크기가 커질수록, penalty를 먹입니다(즉, 작은 subgraph일...

what is load centrality? networkx documentation에 작성된 "load centrality"는 다음과 같습니다. The load centrality of a node is the fraction of all sh...

[PaperSummary] Axioms for Centrality 논문 링크 Abstract 번역 Given a social network, which of its nodes are more central? This question has bee...

Subgraph Centrality in Complex Networks 2005년에 나온 논문입니다. 논문의 링크 Abstract 번역 We introduce a new centrality measure that characterizes the ...

centrality - local reaching centrality. "local reaching centrality"는 말 그대로, "접근가능성"을 활용하여, node의 중심성을 평가합니다. node 의 local reaching centra...

Percolation은 한국말로 "여과"입니다. 커피를 만들때 필터에 커피를 투과시키는 것을 보통 여과라고 하죠. 그리고, node 의 Percolation centrality는 해당 노드를 지나가는 "percolated path(여과된 길)"의...

community detection 방법은 네트워크에서 보다 긴밀한 관계를 가지는, 노드 그룹을 뽑아내는 방법을 말합니다. 특히, girvan newman method는 가장 가치가 높은 edge를 순차적으로 잘라나가면서 group을 계층적으로 ...

centrality - dispersion "dispersion"은 Romantic Partnerships and the Dispersion of Social Ties에서 제안한 개념으로, 기존의 embeddedness와 약간은 다른 개념입니다....

페이스북 직원과 코넬대학교의 연구자가 같이 연구해서 발표한 저작물이군요. 제목을 번역한다면, "페이스북의 'relationship status'에 대한 네트워크 분석"이 되겠군요. 논문 링크 Abstract 번역 A crucial task in ...

What is Configuration model. Configuration model은 Node들에 대한 Degree sequence가 주어졌을 때, degree sequence를 그대로 유지한 상태로, random network를 만드는 방법...

intro - community evaluation. graph에서 내부에 존재하는 다양한 소그룹, 이른바 community를 뽑아내었다고 해봅시다. 가령 "방법1로 community를 도출한 경우", "방법2로 community를 도출한 경우"...

1-line summary girvan-newman method말고, networkx - greedy modularity communities를 사용하면, 훨--씬 빠르게, 더 높은 modularity를 가지는 community 집단을 뽑아낼 수...

3-line summary modularity는 네트워크에서 클러스터링을 수행했을 때, 얼마나 잘 나누었는지를 측정하기 위한 지표. configuration model을 null model로 하여 random할때보다 얼마나 더 차이가 있는지를 비...

1-line summary "Adamic/Adar index"는 "Resource Allocation Index"와 매우 유사하나, 각 값에 log를 취해서 더해준다는 차이만 있음. Adamic Adar index 개념이 매우 간단하므로 pyth...

2-line summary jaccard coeffcient는 (두 집합간의 intersection set)/(두 집합간의 union set)임. 매우 간단하며, 네트워크뿐만 아니라 일반적인 data mining쪽에서도 "거리"등을 측정하기 위해...

3-line summary preferentail attachment는 이른바 "빈익빈 부익부"를 말하며, "강한 놈은 더 강해진다"라는 의미죠. 네트워크에서도 동일하며, 새로 발생할 가능성이 높은 link는 아마도, "힘이 쎈 노드들일 수록 붙...

3 line-summary 에서 제공하는 clique 관련 함수들을 정리하였습니다. clique는 graph내에 존재하는 complete-subgraph를 말함. 매우 기본적인 graph의 특성이며, 각 노드가 어떤, 그리고 몇 개의 clique...

2-line summary Graph에서 에 근거한 다양한 함수들을 정리함. , , 등 매우 기본적인 graph의 기본적인 지표 및 개념들 정리. Do it using 어려운 코드가 아니어서, 아래에 그대로 정리하였습니다. reference ne...

3-line summary pagerank, katz centrality, bewteenness centrality 등 graph의 global structure에 기반한 link prediction이 많지만, common neighbor와 같은...

3-line summary. 네트워크에서 component)는 "connected component"라고 불리기도 하며, "집단 내 어떤 두 노드 사이에도 path가 존재하는 집단"을 보통 말한다. networkx - component compo...

3-line summary SimRank는 "비슷한 사람에 의해서 가리켜지면, 비슷한 사람일 것이다"라는 가정에 기반한 node, similarity 계산법. 여기서 중요한 것은 "비슷한"이라는 말로, recursive의 형태로 "비슷함"을 적용...

2-line summary node끼리 서로 양방향으로 path가 모두 있는 것이 strong-connectivity. 한 방향만 있는 것이 weak-connectivity. strong connectivity https://en.wikipedi...

intro. networkx - algorithms - isolates에 있는 내용을 정리합니다. 사실, 우리가 다루는 네트워크에서, "어떤 노드와도 연결되어 있지 않은 node"를 "isolate"라고 합니다. . networkx 다음의 함수들...

line summary HITS는 webpage들은 hub(포탈 사이트), authoriy(파워블로그)로 구분할 수 있다는 가정하에서, 각 페이지별로, 이 값을 계산하면서 상호 재귀 방식(mutual recursion)으로 값을 계산한다. 모든 ...

2-line summary for PageRank pagerank는 "(web)Page의 순위(Rank)를 매기는 방법"을 말하며, page를 노드로 in-link, out-link를 edge로 고려하여 그래프를 만들고, 그래프에 기반해 node...

line summary "label propagation"은 내 이웃들이 많이 속한 label이, 내 label이다, 라는 접근으로, 직관적인 개념에 기반하여 community을 만들어 나감. async Label Propagation Label...

3-line summary async label propagation은 매우 오래 걸리고, sync 방법은, bipartite network에서 발산하는 경우가 있어서, Community Detection via Semi-Synchronous L...

line summary. What is Graph Coloring? Graph coloring은, 말 그대로 "Graph에 색칠을 하는 것"을 말합니다. 단, 여기서 필요한 색깔의 수 를 최소화하는 것을 보통 목적으로 하죠. 그리고 node를 색...

3-line summary. "어떤 네트워크가 어떠한 성질을 가진다"는 것을 증명하기 위해서는 보통 비슷한 성질을 가지는, random network를 reference로 삼는다. graph의 small-worldness를 측정하기 위해서는 'e...

3-line summary small-world network는 "높은 clustering", "짧은 average shortest path lenght"를 가진다. 따라서, lattice network(highly clustered, long ...

1-line summary. "lattice network"는 삼각형/사각형/육각형 등으로 벌집처럼 촘촘하게 만들어낸 네트워크 구조를 말합니다. 를 통해 간단하게 사용할 수 있습니다. lattice network. google에서 "lattice...

2-line summary 는 graph 에서 최소한 의 node degree를 가지는 subgraph를 말합니다. 그냥 순차적으로 k보다 node degree가 작은 node를 잘라나가면 찾을 수 있습니다(혹은 존재하지 않거나). what is...

2-line summary. 는 equivalent random network와 equivalent lattice network라는 두 reference network를 기준으로 평균 최단거리, clustering을 각각 비교하여 균형을 맞추고 ...

2-line summary. 는 equivalent random network를 기준으로 clustering, 평균 최단거리를 비교하여, 만들어진 지표. 1.0이 넘으면 보통 small-world라고 하지만, 그래프의 크기가 충분히 커지면 유효하...

2-line summary 알고리즘은, 가령 influencer들을 통해 모든 네트워크를 커버하려고 할 때, 서로 겹치지 않게 하려면 어떻게 하는 것이 제일 좋은가? 를 보여준 알고리즘. 그냥 "이웃들에게 투표를 하는 알고리즘"이며, 선택되고 나...

What is small-world network Small-world Network는 대부분의 노드가 서로 이웃은 아니지만, 어떤 노드도 다른 노드들의 이웃이 될 가능성이 있고(link prediction이 높고), 대부분의 노드가 다른 노드로...

2-line summary corenumber는 각 vertex가 속할 수 있는 가장 큰 k-core의 를 말함. 따라서, k-core를 찾아가면서, 속해 있으면 update하는 식으로 처리하면 됨. core-number core-number는 ...

1-line summary 를 사용해서, power of graph를 만들 수 있다. power of graph k power of graph 는 마코브체인처럼, 노드들이 번만에 도달할 수 있으면, 서로 인접하다고 보는 것이죠. 물론, 그러함으로...

1-line summary 는 "k-떨거지"라고 말해도 되는데, 기존 graph 에서, k-core를 제거한 subgraph를 말하죠. k-crust. 즉, 는 를 제거했을 때, 남는 complement graph라고 보셔도 됩니다. 다만, 에서...

2-line summary 은 "core number를 로 가지는 node들의 subgraph, 그리고, (k+1)-core에 존재하지 않는 노드들을 말하죠" 사실, 별거 아닌것 같은데, 종종 complex network에서 node들의 계층적인...

2-line summary 은 "core number를 로 가지는 node들의 subgraph, 그리고, (k+1)-core에 존재하지 않는 노드들을 말하죠" 사실, 별거 아닌것 같은데, 종종 complex network에서 node들의 계층적인...

2-line summary graph 의 complement 는 "+ = complemet graph"라고 생각하면 됨. Directed graph 의 는 방향성을 반대로 하는 것을 말함( ==> ) complement of graph 의 com...

1-line summary graph binary operator, 즉, 그래프에 대한 덧셈 뺄셉을 정리했습니다. 사실, 집합 개념과 동일해요. graph binary operator Graph에 대해서 적용할 수 있는 operator들, 즉, ...

2-line summary graph 의 node간 연결성을 체크하는 방법중에서 가 보다 2배 이상 빠름. 물론, 를 사용하면, 더 빨라지지만, 위험성이 있으므로 가급적 하지 않는 것을 추천. 는 보다 빠른가? 저는 보통 node들의 연결성(ed...

2-line summary 이전에 언급했던, harmonic function과 유사합니다만, localness(가까운 이웃들과의 관계), globalness(네트워크 전체를 봤을때, 지역적인 구분)에 대한 관점을 를 통해 결정할 수 있따, 라는 ...

1-line summary Before: (u, v) and (x, y) AFter : (u, x) and (v, y) network - double edge swap network의 유형, 특성들을 판단하는 지표들의 유효함을 보이기 위해서는 보...

2-line summary 를 그냥 으로 변환해주면 weight를 고려하지 못한다는 문제가 있음. 따라서, weight를 고려하여 를 만들어주는 함수를 정의. MultiGraph to Graph MultiGraph는 보통 노드 에서 노드 로 가는...

2-line summary. 를 사용해서 figure에 연속해서 그려지는 그림을 animation으로 표현하는 방법을 정리하였습니다. : 에 "그리는 방법"을 정의하고, 로 매 그림마다 필요한 데이터는 iterator의 형식으로 넘겨줍니다. in...

3-line summary 는 "k-core에 대한 density 변화율"을 의미함. equivalent random network와 비교하여 normalization. 와 동일한 코드를 다른 형태로 만들어봄. What is Rich Club? ...

network theory에서 bridge란, "해당 edge가 끊어지면, graph의 connected component가 증가하는 edge"를 말합니다. 즉, edge 가 끊어진다면, node , 는 어떠한 방법으로도 서로 도달할 수가 없는 ...

2-line summary 알고리즘은, 가령 influencer들을 통해 네트워크를 최대한 많이 커버하려고 할 때, 서로 겹치지 않게 influencer들을 선택하려면 어떻게 하는 것이 제일 좋은가? 를 보여준 알고리즘. 그냥 "이웃들에게 반복적...

1-line summary closeness vitality Closeness vitality Closeness vitality는 번역하자면, "근접 생명력/필수"처럼 번역될텐데, 의미가 이상해지는 군요. 계산방법으로 보면, 이는 특정 노드가 해...

2-line summary shortest path with weight. 오늘 이야기할 것은 사실 좀 사소한 것일 수도 있습니다. 보통 를 이용해서 분석을 할 때, 를 고려하고 싶은 경우에는 의 형태로 argument를 넘겨줍니다. 보통 이렇게...

Wienerindex Wiener index는 chemical graph theory에서 등장하는데, 하나의 chemical graph 내에 등장하는 모든 node pair간의 shortest-path-length의 합을 말합니다. 개념상, 복잡...

4-line summary structural hole은 "그래프에서 구조적인 허점"을 말하며, 이 "구조적인 허점"에 존재하는 node들은 보통 서로 다른 클러스터의 중심에 위치하게 되므로 정보의 중개자로서 강한 이득을 얻게 된다는 것을 말합니...

2-line summary effective-size는 "redundancy"를 중심 개념으로 "node u에서 v로 가는 중복된 path가 존재하는가"를 중심으로 값을 계산합니다. 특히, ego-network를 중심으로 star-graph와 가...

Structual Hole vs. bet centrality. structural hole은 이른바 "구조적 구멍"이라고 많이 말해지는데요, 어떤 네트워크 내에서 서로 다른 두 클러스터의 중간에서, 중간자로서의 역할을 하게 될 경우, 해당 노드는...

1-line summary 은 graph 에서 "source로부터 target까지 가지는 모든 중복없는 노드 traversal"을 리턴. allsimplepath. graph에서 path는 중복 없는 노드 traversal을 말합니다. 특정 시작...

1-line summary network에 대해서 DFS(depth-first-search), BFS(Breadth-first-search)를 generator를 사용하여 구현함. DFS(Depth-First-Search) 네트워크를 깊이 중심으...

1-line summary "chain decomposition"은 edge partition의 방법 중 하나로, DFS의 결과로 생성된 Tree를 고려하여, Tree에 속하지 않은 nontree edge을 순차적으로 읽으면서 만들 수 있는 cy...

3-line summary textRank는 pagerank를 text에 접목시킨 것이다. 이 때 사용하는 Graph는 word를 node로 하여 문장 내 공동출현 값을 edge의 weight로 주는 경우가 있고 혹은 sentence를 node로...

networkx.multigraph 사용하기. 의 경우 network(Graph)를 방향성(directionality), 다중-Edge-가능여부에 따라 총 4가지로 구분하죠. nx.Graph() : 방향성이 없고, node간에 하나의 edge만 ...

network에서 centrality를 계산할 때, 기본적으로는 edge의 weight를 모두 1로 가정합니다. 이럴 때는 상관없지만, weight 값에 따라서, centrality가 달라질 때, 그냥 아무 생각없이 weight를 그대로 넘겨주지...

networkx - Subgraph. networkx에서 어떤 현상을 Graph로 모델링한 다음, 어떤 부분만 특정하게 보고 싶을 때가 있습니다. 가령, "특정 노드들"만 포함되거나, "특정 Edge들"만 포함되거나, 하는 식으로 보고 싶을 때가...

networkx - closeness centrality network에서 closeness centrality는 "노드 u에서 다른 모든 노드들까지의 거리의 합의 역수"를 말합니다. 즉, closeness centrality가 높으면, 다른 모...

networkx - centrality with weight network에서 중요한 Node를 추출하기 위하여, centrality를 분석합니다. 보통은 Network 상에서 node간의 거리를 활용하여 이 centrality를 계산하게 되죠....

networkx - centrality with weight 어떤 대상/현상을 네트워크로 모델링한 뒤, 보통 "그래서 가장 중요한 Node/Edge가 무엇인가?"를 찾는 작업을 많이 합니다. 이 작업을 보통 Centrality 분석 이라고 하죠....

networkx - MultiGraph에 대해서 Centrality 계산하기 networkx에서는 Graph를 총 4가지 방법으로 표현할 수 있습니다. 방향성(Directionality) 그리고 Multiple-Edge에 따라서 2개로 나누어 ,...

저는 대상/현상을 네트워크로 모델링하고 네트워크 적인 분석 법을 사용하여 대상 네트워크를 분석하는 일을 주로 수행합니다. 그리고, 그러다보니, 세상의 많은 현상들을 결국 "네트워크"적으로 바라보게 되죠. 동시에 저는, 한국 힙합의 오랜 팬이기도 ...

한국 힙합씬 피쳐링 네트워크 분석. 저는 대상/현상을 네트워크로 모델링하고 네트워크 적인 분석 법을 사용하여 대상 네트워크를 분석하는 일을 주로 수행합니다. 그리고, 그러다보니, 세상의 많은 현상들을 결국 "네트워크"적으로 바라보게 되죠. 동시에...

한국 힙합씬 피쳐링 네트워크 분석. 저는 대상/현상을 네트워크로 모델링하고 네트워크 적인 분석 법을 사용하여 대상 네트워크를 분석하는 일을 주로 수행합니다. 그리고, 그러다보니, 세상의 많은 현상들을 결국 "네트워크"적으로 바라보게 되죠. 동시에...

Intro node의 uniqueness가 보장되지 않은 network를 대상으로 network 분석을 수행하고 있습니다. node의 uniqueness가 보장되지 않았다는 말은, "현재의 network에서 서로 다르게 표현된 두 node가 정말...

reference networkx.algorithms.centrality.secondordercentrality

HiphopLE에 올라온 17만 개의 글을 분석하여 이런저런 분석을 수행해 봤습니다. HiphopLE Analysis에서 자세한 내용을 볼 수 있습니다. 이 글에서는 좀 더 세부적인 내용들을 정리합니다. Intro 과거에는 다음 분석 자료를 공유...