Print

Print


*****  To join INSNA, visit http://www.insna.org  *****

 


Not sure if I understand your question fully.

The amount of maximum flow is unique but it could be achieved in a number of
different ways. The way Freeman and Borgatti get over this is to see to what
extent an individual node must contribute to this. Algorithmically the node
is deleted and the maximum flow re-calculated. This means the non-uniqueness
is no longer a problem but the algorithm is slow. I cannot recall the
definition but Lin and Steve may not have formulated it so that it matched
their algorithm exactly.

Any book will tell you that the algorithm finds a maximum flow not the
maximum flow. 


Martin Everett
Marylebone Provost	
University of Westminster
35 Marylebone Road
London NW1 5LS

Email [log in to unmask]
Tel +44(0)20 7911 5010
Fax +44(0)20 7911 5051

This e-mail and its attachments are intended for the above named only and
may be confidential.  If they have come to you in error you must not copy or
show them to anyone, nor should you take any action based on them, other
than to notify the error by replying to the sender.


-----Original Message-----
From: Social Networks Discussion Forum [mailto:[log in to unmask]] On
Behalf Of Kim Se Kwon
Sent: 20 December 2005 09:33
To: [log in to unmask]
Subject: Non unique maximum flow network problem in calculating flow
betweenness.

*****  To join INSNA, visit http://www.insna.org  *****

Hi, socnetters.

In Newman's random walk betweenenss centrality paper (A measure of
betweenness centrality based on random walks. M. E. J. Newman. 
arXiv:cond-mat/0309045 v1. 1 sep 2003.), there is notes like this in page 3
about flow betweenness centrality :

   "Technically, this definition (of flow betweenness) is not unique,
because there need not be a unique solution to the flow problem. To get
around this difficulty, Freeman et al. define their betweenness measure as
the the maximum possible flow through i over all possible solutions to the
st maximum flow problem, averaged over all s and t."

   Because maximum flow network is not uniquely determined, that problem is
occured. But... are there any algorithm that enable the calculation (:the
maximum possible flow through i over all possible solutions to the st
maximum flow problem) mentioned in notes? I haven't heard any comment about
the problem in algorithm courses or books.

Thank you for any comments. 



Best Regards
Se Kwon, Kim

-------------
KAIST (Korean Advanced Institute of Science & Technology) Mathematics
Student http://math.kaist.ac.kr

_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send an email
message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in
the body of the message.

_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.