Does anybody have the code for PageRank-Nibble algorithm preferably for Python or Java? i've got SNAPY and NetworKit(a really interesting tool) and Graph-tool(it's very fast) and NetworkX(it's really nice and thorough but a bit slow), and had to go through their documentations but i couldn't find a reference on PageRank-Nibble for Python in none of them, so i was to ask, does anybody may've got a clue where to search for its code? is there any Python or other high level language implementation of this particular algorithm? btw any suggestion or help is very much appreciated.
These works are probably related to what you are looking for: https://github.com/digmaa/HeadTailCommunityDetection
Jiang B. and Ma D. (2015), Defining least community as a homogeneous group in complex networks, Physica A: Statistical Mechanics and its Applications, 428, 154-160, Preprint: http://arxiv.org/ftp/arxiv/papers/1502/1502.00284.pdf
Jiang B., Duan Y., Lu F., Yang T. and Zhao J. (2014), Topological structure of urban street networks from the perspective of degree correlations, Environment and Planning B: Planning and Design, 41(5), 813-828.
The beauty of your question is to design an algorithm that can do that. You might end up designing something really amazing and insightful. Let me know if you would like to discuss this further!
The gephi toolkit implenents nethods for community detection.
I used its Louvain method implementation
thanks @Marco_Querini, I consider this problem solved now,
https://github.com/habedi/-myPython-LanguageCodes/blob/master/codes/personalized_pagerank.py
I am a new in the field of Data Science , Could someone help me with a community detection algorithm in pyhton code?
Community detection instructions
I. The implementation of community detection, you can work on Python, C++, Java, R, or Other programming language
II. You can use library to implement this homework
III. The homework is due on 6/15/2018
Evaluation Description
The scoring metrics is Categorization Accuracy
Submission Format
The submission file should contain a header(as below example), id column represent the pair id in the question.txt,prediction column represent this pair is in the same community or not,You should predict by yourself，1=yes，0=no，The data looks like following:
Example:
id,prediction
0,1
1,0
2,0
File descriptions
email-Eu-core.txt is the historical data of email transmissions between a company for use in drawing
question.txt is a question that you need to answer. The id column represents the index. node_1 and node_2 represent a pair. After classifying the community, you need to determine whether the pair is in the same community or not.
question.txt
l id – pair’s index
l node_1 – first node in the pair
l node_2 – second node in the pair
email-Eu-core.txt
Each line represent the first node connected to the second node
method:
Step1. Use the email-Eu-core.txt to draw the graph(igraph, networkx)
Step2. Use community detection algorithm to classifying the community
Step3. Answer each pair in the question.txt is in the same community or not
Step4. Notice that the submission file only need the pair id and prediction result
Following is a link of kaggle competition:
https://www.kaggle.com/t/f7b345bbec2c4cc98c237e54c712ba36
I have this but the answer is
raise NetworkXError("The node %s is not in the graph." % (n,))
networkx.exception.NetworkXError: The node 5 is not in the graph.
I am not sure it's rigth or not. The node number 5 is not in the first community?
import networkx as nx
from operator import itemgetter
from collections import OrderedDict
import numpy as np
import sys
import csv
import networkx as nx
import tkinter
from operator import itemgetter
with open('email-Eu-core1.csv', 'r') as nodecsv: # Open the file
nodereader = csv.reader(nodecsv) # Read the csv
# Retrieve the data (using Python list comprhension and list slicing to remove the header row, see footnote 3)
nodes = [n for n in nodereader][1:]
node_names = [n[0] for n in nodes] # Get a list of only the node names
with open('email-Eu-core1.csv', 'r') as edgecsv: # Open the file
edgereader = csv.reader(edgecsv) # Read the csv
edges = [tuple(e) for e in edgereader][1:] # Retrieve the data
#print(len(node_names))
#print(len(edges))
g = nx.Graph()
g.add_nodes_from(node_names)
g.add_edges_from(edges)
def saludar(nombre, mensaje='Hola'):
print (mensaje, nombre)
saludar(mensaje="Buen día", nombre="Juancho")
print(nx.info(g))
n=len(g)
print(n)
v=len(g.edges())
print(v)
def ppr(g, seed, alpha=0.85, epsilon=10e-8, iters=100):
pref = {}
T = [seed]
for node in g.neighbors(seed):
T.append(node)
for node in g:
if node in T:
pref.update({node:(1.0 / len(T))})
else:
pref.update({node:0.0})
return nx.pagerank(g, alpha=alpha, personalization=pref, max_iter=iters,
tol=epsilon)
def ppr_sorted(g, pprv):
spprv = {}
for item in pprv.iteritems():
k, v = item
spprv.update({k:(v/g.degree(k))})
pass
return sorted(spprv.items(), key=itemgetter(1), reverse=True)
def min_cond_cut(g, dspprv, max_cutsize=0):
def conductance(nbunch):
sigma = 0.0
vol1 = vol2 = 0
for node in nbunch:
for n in g.neighbors(node):
if n not in nbunch:
sigma += 1.0
for degseq in g.degree().iteritems():
node, degree = degseq
if node not in nbunch:
vol2 += degree
else:
vol1 += degree
return (sigma / min(vol1, vol2))
k = 1
conductance_list = []
if max_cutsize < 1:
# cutsize could be as big as the graph itself
limit = (len(dspprv))
else:
# maximum size of the cut with minimum conductance
limit = max_cutsize
while k < limit :
nbunch = []
for i in xrange(0, k):
nbunch.append(dspprv[i][0])
c = (k, conductance(nbunch))
# conductane of current cut size
print(c)
conductance_list.append(c)
k += 1
return min(conductance_list, key=itemgetter(1))
## running the code ..
def loadGraph(gfile):
return nx.read_edgelist(path=gfile, comments='#',
delimiter="\t", nodetype=int)
g = loadGraph(gfile='question.txt')
a = ppr(g, seed=5, alpha=0.85, epsilon=10e-8, iters=100)
b = ppr_sorted(g, pprv=a)
# finding the best community around NodeId==5
print(min_cond_cut(g, dspprv=b, max_cutsize=10))
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Programming Languages
- Python