Re: [Boost-users] Graph Structural Information

Subject: Re: [Boost-users] Graph Structural Information
From: Nouf M. (noufmks_at_[hidden])
Date: 2012-03-05 06:32:48

 Hello,

Thank you for your prompt reply...

The two graphs models social networks:

Graph 1: vertices are Authors and edges represent the co-author
relationship between two authors.

Graph 2: vertices are Concepts and edges represent concept-concept
relationship between two concepts (i.e. if two concepts occurred together
in a document then there is an edge between two concepts).

Both vertices and edges have weights (in both graphs)…

Both graphs have millions of nodes and edges. My work involves finding a
subgraph that best describes the connection between two given vertices.

I want to choose the graph that best represents the real world. i.e. its
structural characteristics is similar to the structural characteristics of
the majority of real world graph. e.g. the degree distribution is similar
to the degree distribution of real graphs...

 In my readings, I found that real-world Social graphs are usually well
connected and have a short average path length and have exceptionally large
clustering coefficients.

Can Boost find these things for me? Is th?ere any other measures to choose
a graph that best represents real world graphs

Best regards,
Nouf

On Sun, Mar 4, 2012 at 9:20 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Sun, 4 Mar 2012, Nouf M. wrote:
>
>  Hello,
>>
>> I have two very huge graphs, I need to select one to work with. Both
>> graphs have one node type and one edge type. Both also have the same
>> semantic meaning. Therefore, my choice should depend on some structural
>> characteristics (e.g. degree distribution)...
>>
>> I so that BGL can provide me with the degree distribution in a manual
>> way...
>>
>> I have two questions:
>> Is there some specific functions that I can call to give me all
>> structural characteristics of a graph?
>>
>
> I don't know what structural characteristics you are interested in; if you
> gave me a list, I might be able to be more helpful.
>
>
>  If not, what do you recommend I should look for other than the degree
>> distribution to make up my choice? I cannot make a random choice...
>>
>
> I don't know your problem domain.  What would make you choose one of the
> graphs over the other?  What do you want to do to whichever graph you
> choose?
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>