easygraph.functions.structural_holes package

Submodules

easygraph.functions.structural_holes.AP_Greedy module

easygraph.functions.structural_holes.AP_Greedy.AP_Greedy(G, k, c=1.0, weight='weight')

AP greedy method for structural hole spanners detection.

Returns top k nodes as structural hole spanners, Algorithm 2 of [1]_

Parameters:

• G (easygraph.Graph) – An undirected graph.

• k (int) – top - k structural hole spanners

• c (float, optional (default : 1.0)) – To define zeta: zeta = c * (n*n*n), and zeta is the large value assigned as the shortest distance of two unreachable vertices. Default is 1.

• weight (String or None, optional (default : 'weight')) – Key for edge weight. None if not concerning about edge weight.

Returns:

AP_greedy – The list of each top-k structural hole spanners.

Return type:

list

Examples

Returns the top k nodes as structural hole spanners, using AP_greedy.

>>> AP_greedy(G,
...           k = 3, # To find top three structural holes spanners.
...           c = 1.0, # To define zeta: zeta = c * (n*n*n), and zeta is the large value assigned as the shortest distance of two unreachable vertices.
...           weight = 'weight')

References

[1]

https://dl.acm.org/profile/81484650642

easygraph.functions.structural_holes.AP_Greedy.common_greedy(G, k, c=1.0, weight='weight')

Common greedy method for structural hole spanners detection.

Returns top k nodes as structural hole spanners, Algorithm 1 of [1]_

Parameters:

• G (easygraph.Graph) – An undirected graph.

• k (int) – top - k structural hole spanners

• c (float, optional (default : 1.0)) – To define zeta: zeta = c * (n*n*n), and zeta is the large value assigned as the shortest distance of two unreachable vertices. Default is 1.

• weight (String or None, optional (default : 'weight')) – Key for edge weight. None if not concerning about edge weight.

Returns:

common_greedy – The list of each top-k structural hole spanners.

Return type:

list

See also

AP_Greedy

Examples

Returns the top k nodes as structural hole spanners, using common_greedy.

>>> common_greedy(G,
...               k = 3, # To find top three structural holes spanners.
...               c = 1.0, # To define zeta: zeta = c * (n*n*n), and zeta is the large value assigned as the shortest distance of two unreachable vertices.
...               weight = 'weight')

References

[1]

https://dl.acm.org/profile/81484650642

easygraph.functions.structural_holes.HAM module

easygraph.functions.structural_holes.HAM.get_structural_holes_HAM(G, k, c, ground_truth_labels)

Structural hole spanners detection via HAM method.

Using HAM [1]_ to jointly detect SHS and communities.

Parameters:

• G (easygraph.Graph) – An undirected graph.

• k (int) – top - k structural hole spanners

• c (int) – the number of communities

• ground_truth_labels (list of lists) – The label of each node’s community.

Returns:

• top_k_nodes (list) – The top-k structural hole spanners.

• SH_score (dict) – The structural hole spanners score for each node, given by HAM.

• cmnt_labels (dict) – The communities label of each node.

Examples

>>> get_structural_holes_HAM(G,
...                         k = 2, # To find top two structural holes spanners.
...                          c = 2,
...                          ground_truth_labels = [[0], [0], [1], [0], [1]] # The ground truth labels for each node - community detection result, for example.
...                         )

References

[1]

https://dl.acm.org/doi/10.1145/2939672.2939807

easygraph.functions.structural_holes.HIS module

easygraph.functions.structural_holes.HIS.get_structural_holes_HIS(G, C: List[frozenset], epsilon=0.0001, weight='weight')

Structural hole spanners detection via HIS method.

Both HIS and MaxD are methods in [1]_. The authors developed these two methods to find the structural holes spanners, based on theory of information diffusion.

Returns the value of S, I, H ,defined in HIS of [1], of each node in the graph. Note that H quantifies the possibility that a node is a structural hole spanner. To use HIS method, you should provide the community detection result as parameter.

Parameters:

• C (list of frozenset) – Each frozenset denotes a community of nodes.

• epsilon (float) – The threshold value.

• weight (string, optional (default : 'weight')) – The key for edge weight.

Returns:

• S (list of tuple) – The S value in [1]_.

• I (float) – The I value in [1]_.

• H (float) – The H value in [1]_.

See also

MaxD

Examples

>>> get_structural_holes_HIS(G,
...                          C = [frozenset([1,2,3]), frozenset([4,5,6])], # Two communities
...                          epsilon = 0.01,
...                          weight = 'weight'
...                          )

References

[1]

https://www.aminer.cn/structural-hole

easygraph.functions.structural_holes.ICC module

easygraph.functions.structural_holes.ICC.AP_BICC(G, k, K, l)

an efficient algorithm for structural hole spanners detection.

Returns top k nodes as structural hole spanners, Algorithm 3 of [1]_

Parameters:

• G (easygraph.Graph) – An unweighted and undirected graph.

• k (int) – top - k structural hole spanners

• K (int) – the number of candidates K for the top-k hole spanners

• l (int) – level-l neighbors of nodes

Returns:

V – The list of top-k structural hole spanners.

Return type:

list

Examples

Returns the top k nodes as structural hole spanners, using AP_BICC.

>>> AP_BICC(G,k=3,K=5,l=4)

References

[1]

https://dl.acm.org/doi/10.1145/2806416.2806431

easygraph.functions.structural_holes.ICC.BICC(G, k, K, l)

an efficient algorithm for structural hole spanners detection.

Returns top k nodes as structural hole spanners, Algorithm 2 of [1]_

Parameters:

• G (easygraph.Graph) – An unweighted and undirected graph.

• k (int) – top - k structural hole spanners

• K (int) – the number of candidates K for the top-k hole spanners

• l (int) – level-l neighbors of nodes

Returns:

V – The list of top-k structural hole spanners.

Return type:

list

Examples

Returns the top k nodes as structural hole spanners, using BICC.

>>> BICC(G,k=3,K=5,l=4)

References

[1]

https://dl.acm.org/doi/10.1145/2806416.2806431

easygraph.functions.structural_holes.ICC.ICC(G, k)

an efficient algorithm for structural hole spanners detection.

Returns top k nodes as structural hole spanners, Algorithm 1 of [1]_

Parameters:

• G (easygraph.Graph) – An unweighted and undirected graph.

• k (int) – top - k structural hole spanners

Returns:

V – The list of top-k structural hole spanners.

Return type:

list

Examples

Returns the top k nodes as structural hole spanners, using ICC.

>>> ICC(G,k=3)

References

[1]

https://dl.acm.org/doi/10.1145/2806416.2806431

easygraph.functions.structural_holes.MaxD module

easygraph.functions.structural_holes.MaxD.get_structural_holes_MaxD(G, k, C: List[frozenset])

Structural hole spanners detection via MaxD method.

Both HIS and MaxD are methods in [1]_. The authors developed these two methods to find the structural holes spanners, based on theory of information diffusion.

Parameters:

• k (int) – Top-k structural hole spanners

• C (list of frozenset) – Each frozenset denotes a community of nodes.

Returns:

get_structural_holes_MaxD – Top-k structural hole spanners

Return type:

list

Examples

>>> get_structural_holes_MaxD(G,
...                           k = 5, # To find top five structural holes spanners.
...                           C = [frozenset([1,2,3]), frozenset([4,5,6])] # Two communities
...                           )

References

[1]

https://www.aminer.cn/structural-hole

easygraph.functions.structural_holes.NOBE module

easygraph.functions.structural_holes.NOBE.NOBE_GA_SH(G, K, topk)

detect SH spanners via NOBE-GA[1].

Parameters:

• G (easygraph.Graph) – An unweighted and undirected graph.

• K (int) – Embedding dimension k

• topk (int) – top - k structural hole spanners

Returns:

SHS – The top-k structural hole spanners.

Return type:

list

Examples

>>> NOBE_GA_SH(G,K=8,topk=5)

References

[1]

https://www.researchgate.net/publication/325004496_On_Spectral_Graph_Embedding_A_Non-Backtracking_Perspective_and_Graph_Approximation

easygraph.functions.structural_holes.NOBE.NOBE_SH(G, K, topk)

detect SH spanners via NOBE[1].

Parameters:

• G (easygraph.Graph) – An unweighted and undirected graph.

• K (int) – Embedding dimension k

• topk (int) – top - k structural hole spanners

Returns:

SHS – The top-k structural hole spanners.

Return type:

list

Examples

>>> NOBE_SH(G,K=8,topk=5)

References

[1]

https://www.researchgate.net/publication/325004496_On_Spectral_Graph_Embedding_A_Non-Backtracking_Perspective_and_Graph_Approximation

easygraph.functions.structural_holes.SHII_metric module

class easygraph.functions.structural_holes.SHII_metric.NodeParams(active, inWeight, threshold)

Bases: object

easygraph.functions.structural_holes.SHII_metric.structural_hole_influence_index(G_original, S, C, model, variant=False, seedRatio=0.05, randSeedIter=10, countIterations=100, Directed=True)

Returns the SHII metric of each seed.

Parameters:

• G_original (easygraph.Graph or easygraph.DiGraph)

• S (list of int) – A list of nodes which are structural hole spanners.

• C (list of list) – Each list includes the nodes in one community.

• model (string) – Propagation Model. Should be IC or LT.

• variant (bool, default is False) – Whether returns variant SHII ml_metrics or not. variant SHII = # of the influenced outsider / # of the influenced insiders SHII = # of the influenced outsiders / # of the total influenced nodes

• seedRatio (float, default is 0.05) – # of sampled seeds / # of nodes of the community that the given SHS belongs to.

• randSeedIter (int, default is 10) – How many iterations to sample seeds.

• countIterations (int default is 100) – Number of monte carlo simulations to be used.

• Directed (bool, default is True) – Whether the graph is directed or not.

Returns:

seed_shii_pair – the SHII metric of each seed

Return type:

dict

Examples

# >>> structural_hole_influence_index(G, [3, 20, 9], Com, ‘LT’, seedRatio=0.1, Directed=False)

References

[1]

https://dl.acm.org/doi/pdf/10.1145/2939672.2939807

[2]

https://github.com/LifangHe/KDD16_HAM/tree/master/SHII_metric

easygraph.functions.structural_holes.evaluation module

easygraph.functions.structural_holes.evaluation.constraint(G, nodes=None, weight=None, n_workers=None)

Burt’s metric - Constraint. :param G: :type G: easygraph.Graph :param nodes: The nodes you want to calculate. If None, all nodes in G will be calculated. :type nodes: list of nodes or None, optional (default : None) :param weight: The key for edge weight. If None, G will be regarded as unweighted graph. :type weight: string or None, optional (default : None) :param workers: The number of workers calculating (default: None).

None if not using only one worker.

Returns:

constraint – The Constraint of node in nodes.

Return type:

dict

Examples

>>> constraint(G,
...            nodes=[1,2,3], # Compute the Constraint of some nodes. The default is None for all nodes in G.
...            weight='weight', # The weight key of the graph. The default is None for unweighted graph.
...            n_workers=4 # Parallel computing on four workers. The default is None for serial computing.
...            )

References

[1]

Burt R S. Structural holes: The social structure of competition[M]. Harvard university press, 2009.

easygraph.functions.structural_holes.evaluation.effective_size(G, nodes=None, weight=None, n_workers=None)

Burt’s metric - Effective Size. :param G: :type G: easygraph.Graph or easygraph.DiGraph :param nodes: The nodes you want to calculate. If None, all nodes in G will be calculated. :type nodes: list of nodes or None, optional (default : None) :param weight: The key for edge weight. If None, G will be regarded as unweighted graph. :type weight: string or None, optional (default : None)

Returns:

effective_size – The Effective Size of node in nodes.

Return type:

dict

Examples

>>> effective_size(G,
...                nodes=[1,2,3], # Compute the Effective Size of some nodes. The default is None for all nodes in G.
...                weight='weight' # The weight key of the graph. The default is None for unweighted graph.
...                )

References

[1]

Burt R S. Structural holes: The social structure of competition[M]. Harvard university press, 2009.

easygraph.functions.structural_holes.evaluation.efficiency(G, nodes=None, weight=None)

Burt’s metric - Efficiency. :param G: :type G: easygraph.Graph :param nodes: The nodes you want to calculate. If None, all nodes in G will be calculated. :type nodes: list of nodes or None, optional (default : None) :param weight: The key for edge weight. If None, G will be regarded as unweighted graph. :type weight: string or None, optional (default : None)

Returns:

efficiency – The Efficiency of node in nodes.

Return type:

dict

Examples

>>> efficiency(G,
...            nodes=[1,2,3], # Compute the Efficiency of some nodes. The default is None for all nodes in G.
...            weight='weight' # The weight key of the graph. The default is None for unweighted graph.
...            )

References

[1]

Burt R S. Structural holes: The social structure of competition[M]. Harvard university press, 2009.

easygraph.functions.structural_holes.evaluation.hierarchy(G, nodes=None, weight=None, n_workers=None)

Returns the hierarchy of nodes in the graph :param G: :type G: graph :param nodes: :type nodes: dict, optional (default: None) :param weight: :type weight: dict, optional (default: None)

Returns:

hierarchy – the hierarchy of nodes in the graph

Return type:

dict

Examples

Returns the hierarchy of nodes in the graph G >>> hierarchy(G) Reference ——— https://m.book118.com/html/2019/0318/5320024122002021.shtm

easygraph.functions.structural_holes.maxBlock module

easygraph.functions.structural_holes.maxBlock.maxBlock(G, k, f_set=None, delta=1, eps=0.5, c=1, flag_weight=False)

Structural hole spanners detection via maxBlock method.

Parameters:

• G (easygraph.DiGraph)

• k (int) – top - k structural hole spanners.

• f_set (dict, optional) – user vi shares his/her information on network G at a rate fi. default is a random [0,1) integer for each node

• delta (float, optional (default: 1)) – a small value delta > 0.

• eps (float, optional (default: 0.5)) – an error ratio eps with 0 < eps < 1.

• c (int, optional (default: 1)) – Success probability 1-n^-c of maxBlock.

• flag_weight (bool, optional (default: False)) – Denotes whether each edge has attribute ‘weight’

Returns:

S_list – The list of each top-k structural hole spanners.

Return type:

list

See also

maxBlockFast

Examples

# >>> maxBlock(G, 100)

References

[1]

https://doi.org/10.1016/j.ins.2019.07.072

easygraph.functions.structural_holes.maxBlock.maxBlockFast(G, k, f_set=None, L=None, flag_weight=False)

Structural hole spanners detection via maxBlockFast method.

Parameters:

• G (easygraph.DiGraph)

• G

• k (int) – top - k structural hole spanners.

• f_set (dict, optional) – user vi shares his/her information on network G at a rate fi. default is a random [0,1) integer for each node

• L (int, optional (default: log2n)) – Simulation time L for maxBlockFast.

• flag_weight (bool, optional (default: False)) – Denotes whether each edge has attribute ‘weight’

See also

maxBlock

Examples

# >>> maxBlockFast(G, 100)

References

[1]

https://doi.org/10.1016/j.ins.2019.07.072

easygraph.functions.structural_holes.metrics module

easygraph.functions.structural_holes.metrics.nodes_of_max_cc_without_shs(G, S)

Returns the number of nodes in the maximum connected component in graph GS. The experiment ml_metrics in [1]_

Parameters:

• G (easygraph.Graph or easygraph.DiGraph)

• S (list of int) – A list of nodes witch are structural hole spanners.

Returns:

G_S_nodes_of_max_CC – The number of nodes in the maximum connected component in graph GS.

Return type:

int

Examples

>>> G_t=eg.datasets.get_graph_blogcatalog()
>>> S_t=eg.AP_Greedy(G_t, 10000)
>>> maxx = nodes_of_max_cc_without_shs(G_t, S_t)
>>> print(maxx)

References

[1]

https://dl.acm.org/profile/81484650642

easygraph.functions.structural_holes.metrics.structural_hole_influence_index(G_original, S, C, model, variant=False, seedRatio=0.05, randSeedIter=10, countIterations=100, Directed=True)

Returns the SHII metric of each seed.

Parameters:

• G_original (easygraph.Graph or easygraph.DiGraph)

• S (list of int) – A list of nodes which are structural hole spanners.

• C (list of list) – Each list includes the nodes in one community.

• model (string) – Propagation Model. Should be IC or LT.

• variant (bool, default is False) – Whether returns variant SHII ml_metrics or not. variant SHII = # of the influenced outsider / # of the influenced insiders SHII = # of the influenced outsiders / # of the total influenced nodes

• seedRatio (float, default is 0.05) – # of sampled seeds / # of nodes of the community that the given SHS belongs to.

• randSeedIter (int, default is 10) – How many iterations to sample seeds.

• countIterations (int default is 100) – Number of monte carlo simulations to be used.

• Directed (bool, default is True) – Whether the graph is directed or not.

Returns:

seed_shii_pair – the SHII metric of each seed

Return type:

dict

Examples

# >>> structural_hole_influence_index(G, [3, 20, 9], Com, ‘LT’, seedRatio=0.1, Directed=False)

References

[1]

https://dl.acm.org/doi/pdf/10.1145/2939672.2939807

[2]

https://github.com/LifangHe/KDD16_HAM/tree/master/SHII_metric

easygraph.functions.structural_holes.metrics.sum_of_shortest_paths(G, S)

Returns the difference between the sum of lengths of all pairs shortest paths in G and the one in GS. The experiment ml_metrics in [1]_

Parameters:

• G (easygraph.Graph or easygraph.DiGraph)

• S (list of int) – A list of nodes witch are structural hole spanners.

Returns:

differ_between_sum – The difference between the sum of lengths of all pairs shortest paths in G and the one in GS. C(G/S)-C(G)

Return type:

int

Examples

>>> G_t=eg.datasets.get_graph_blogcatalog()
>>> S_t=eg.AP_Greedy(G_t, 10000)
>>> diff = sum_of_shortest_paths(G_t, S_t)
>>> print(diff)

References

[1]

https://dl.acm.org/profile/81484650642

easygraph.functions.structural_holes.weakTie module

easygraph.functions.structural_holes.weakTie.weakTie(G, threshold, k)

Return top-k nodes with highest scores which were computed by WeakTie method.

Parameters:

• G (easygraph.DiGraph)

• k (int) – top - k nodes with highest scores.

• threshold (float) – tie strength threshold.

Returns:

• SHS_list (list) – The list of each nodes with highest scores.

• score_dict (dict) – The score of each node, can be used for WeakTie-Local and WeakTie-Bi.

See also

weakTieLocal

Examples

# >>> SHS_list,score_dict=weakTie(G, 0.2, 3)

References

[1]

Mining Brokers in Dynamic Social Networks. Chonggang Song, Wynne Hsu, Mong Li Lee. Proc. of ACM CIKM, 2015.

easygraph.functions.structural_holes.weakTie.weakTieLocal(G, edges_plus, edges_delete, threshold, score_dict, k)

Find brokers in evolving social networks, utilize the 2-hop neighborhood of an affected node to identify brokers.

Parameters:

• G (easygraph.DiGraph)

• edges_plus (list of list) – set of edges to be added

• edges_delete (list of list) – set of edges to be removed

• threshold (float) – tie strength threshold.

• score_dict (dict) – The score of each node computed before.

• k (int) – top - k nodes with highest scores.

Returns:

SHS_list – The list of each nodes with highest scores.

Return type:

list

See also

weakTie

Examples

# >>> SHS_list=weakTieLocal(G, [[2, 7]], [[1,3]], 0.2, score_dict, 3)

References

[1]

Mining Brokers in Dynamic Social Networks. Chonggang Song, Wynne Hsu, Mong Li Lee. Proc. of ACM CIKM, 2015.

Module contents