Skip to content
Snippets Groups Projects

pydtn agkmeans and version 1.0

Merged Hunter McConnell (rtm534) requested to merge summer2022 into develop
1 file
+ 93
67
Compare changes
  • Side-by-side
  • Inline
+ 93
67
@@ -15,7 +15,6 @@ __all__ = [
"KCliqueCommunity",
"LouvainCommunity",
"AGKmeansCommunity",
"CommunityNode",
"KCliqueNode",
"AGKmeansNode",
@@ -30,7 +29,7 @@ __all__ = [
"HCBFLouvainNode",
]
__author__ = "Jarrod Pas <j.pas@usask.ca>"
__author__ = 'Fatemeh zr <faz361@usask.ca>'
__author__ = "Fatemeh zr <faz361@usask.ca>"
from collections import defaultdict
from itertools import product
@@ -174,9 +173,7 @@ class Community:
if node not in graph:
return 0
return len(
[other for other in node.community if graph.has_edge(node, other)]
)
return len([other for other in node.community if graph.has_edge(node, other)])
def community_betweenness(self, node_a, node_b):
"""Return community betweenness for 2 nodes."""
@@ -202,9 +199,7 @@ class Community:
return 0
return sum(
graph[node_a][b]["weight"]
for b in community_b
if graph.has_edge(node_a, b)
graph[node_a][b]["weight"] for b in community_b if graph.has_edge(node_a, b)
)
@@ -218,9 +213,7 @@ class KCliqueCommunity(Community):
def partition(self):
"""Partition graph by k-clique communities method."""
return nx.algorithms.community.k_clique_communities(
self.graph_old, k=self.k
)
return nx.algorithms.community.k_clique_communities(self.graph_old, k=self.k)
class AGKmeansCommunity(Community):
@@ -234,12 +227,9 @@ class AGKmeansCommunity(Community):
def partition(self):
"""Partition graph by AGk-means communities method."""
graph = nx.Graph()
nodes = {
id(node): node
for node in self.graph_old.nodes()
}
nodes = {id(node): node for node in self.graph_old.nodes()}
graph.add_nodes_from(nodes)
for node_a, node_b, weight in self.graph_old.edges(data='weight'):
for node_a, node_b, weight in self.graph_old.edges(data="weight"):
graph.add_edge(id(node_a), id(node_b), weight=weight)
partitions = agkmeans(graph, k=self.agk)
@@ -319,9 +309,7 @@ class CommunityNode(Node):
def in_community_neighbours(self):
"""Return nodes in my community."""
return [
neighbour
for neighbour in self.neighbours
if neighbour in self.community
neighbour for neighbour in self.neighbours if neighbour in self.community
]
@property
@@ -333,19 +321,20 @@ class CommunityNode(Node):
if neighbour not in self.community
]
def shared_community(context, create):
"""
Check context for shared community and return a shared community.
"""
Check context for shared community and return a shared community.
Use this for community detection algorithms that must have one instance
for a set of nodes.
"""
if "shared-community" in context:
return context["shared-community"]
Use this for community detection algorithms that must have one instance
for a set of nodes.
"""
if "shared-community" in context:
return context["shared-community"]
community = create()
context["shared-community"] = community
return community
community = create()
context["shared-community"] = community
return community
class LouvainNode(CommunityNode):
@@ -396,31 +385,53 @@ class AGKmeansNode(CommunityNode):
epoch -- how often to recalculate communities
k -- initial community size
"""
def _create():
return AGKmeansCommunity(options['epoch'], options['agk'])
options['community'] = shared_community(options['context'], _create)
return AGKmeansCommunity(options["epoch"], options["agk"])
options["community"] = shared_community(options["context"], _create)
super().__init__(**options)
def _decide(node, others, key):
"""
Make a decision on which node to send to best is decided based on key.
"""
Make a decision on which node to send to best is decided based on key.
If the best is better than node, return best.
If node is better than the best, return node.
If the best and node are equal, return None.
"""
best = max(others, key=key)
best_key = key(best)
node_key = key(node)
If the best is better than node, return best.
If node is better than the best, return node.
If the best and node are equal, return None.
"""
best = max(others, key=key)
best_key = key(best)
node_key = key(node)
if best_key > node_key:
return best
if best_key < node_key:
return node
return None
def _tie_breaker(node, others, tiedkey, newkey):
"""
Call after decide returns None to determine the best node based on a second key
"""
best = max(others, key=tiedkey)
tied_list = [node for node in others if tiedkey(node) == tiedkey(best)]
new_best = max(tied_list, key=newkey)
best_key = tiedkey(new_best)
node_key = tiedkey(node)
if best_key > node_key:
return best
if best_key > node_key:
return best
if best_key < node_key:
return node
if best_key < node_key:
return node
return None
return None
class BubbleNode(CommunityNode):
@@ -457,62 +468,83 @@ class BubbleNode(CommunityNode):
class BubbleKCliqueNode(KCliqueNode, BubbleNode):
"""Bubble node with k-clique community detection."""
pass
class BubbleAGKmeansNode(AGKmeansNode, BubbleNode):
"""Bubble node with k-clique community detection."""
pass
class BubbleLouvainNode(LouvainNode, BubbleNode):
"""Bubble node with louvain community detection."""
pass
class HCBFNode(CommunityNode):
"""Node with Hybrid Community Based forwarding."""
def forward(self, packet):
"""Forward packet with Hybrid Community Based heuristic."""
# direct forwarding
# direct forwarding to destination node
forward = super().forward(packet)
if forward:
return forward
dest = packet.destination
# get the packet to the destination community
if self.community != dest.community:
# transmit to the dest community if possible
dest_community_neighbours = [
neighbour
for neighbour in self.out_community_neighbours
if neighbour in dest.community
]
if dest_community_neighbours:
target = _decide(
None,
dest_community_neighbours,
dest._community.unique_interactions,
)
if not (target is None):
return {target: "dest-community-unique-interactions"}
# else, transmit to another community with better betweenness with dest
if self.out_community_neighbours:
cbc = partial(self._community.community_betweenness, dest)
target = _decide(self, self.out_community_neighbours, cbc)
if not (target is None or target is self):
return {target: "community-betweenness"}
# else, within this community, transmit to node with higher nodal contribution with dest
if self.in_community_neighbours:
ncf = partial(self._community.nodal_contribution, dest)
target = _decide(self, self.in_community_neighbours, ncf)
if not (target is None or target is self):
return {target: "nodal-contribution"}
if self.in_community_neighbours:
# the packet is in the destination community, pick the best carrier in this community
elif self.in_community_neighbours:
target = _decide(
self,
self.in_community_neighbours,
self._community.unique_interactions,
)
if not (target is None or target is self):
if target is self: # stay here with the highest UI
return {}
if target is not None: # send to highest UI
return {target: "unique-interactions"}
target = _decide(
self,
self.in_community_neighbours,
self._community.local_popularity,
)
if not (target is None or target is self):
return {target: "local-popularity"}
else: # use LP to break UI ties
target = _tie_breaker(
self,
self.in_community_neighbours,
self._community.unique_interactions,
self._community.local_popularity
)
if not (target is None or target is self):
return {target: "local-popularity"}
return {}
@@ -520,16 +552,10 @@ class HCBFNode(CommunityNode):
class HCBFKCliqueNode(KCliqueNode, HCBFNode):
"""HCBF node with k-clique community detection."""
pass
class HCBFAGKmeansNode(AGKmeansNode, HCBFNode):
"""HCBF node with k-clique community detection."""
pass
class HCBFLouvainNode(LouvainNode, HCBFNode):
"""HCBF node with louvain community detection."""
pass
Loading